Prime Number Program Optimization

[Liviu13]

Hi guys! Today I wrote a program that finds the first 'n' prime numbers and I saw that when 'n' gets bigger, the necessary time for the program to run increases a lot. I found that the most acceptable value for n is 50,000.

I would please like some suggestions on how to make the program run faster.
This is the code:

#include <iostream>

using namespace std;

int main()
{
    int limit, prime, counter;

    cout<<"Introduce a limit: "; cin>>limit;
    cout<<"Prime numbers from 1 to "<<limit<<" are: \n";

    prime = 1; //because 1 is not prime
    counter = 0;

    for(int i = 1; i <= limit; i++)
    {
        prime++;

        for(int j = 2; j <= prime / 2;j++)
        {
            if(prime % j == 0) counter++;
        }

        if(counter == 0) cout<< prime <<endl;
        else counter = 0; //If no prime was found, reinitialize counter.
    }

    return 0;

}

[tipaye]

Consider the sieve of Eratosthenes:
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[Liviu13]

A quick update: I found that if I replace

for(int j = 2; j <= prime / 2;j++)

with for(int j = 2; j <= sqrt(prime);j++) the program runs incredibly fast. I was able to calculate the first 1 million numbers in 37.515 seconds. Please let me know if you have any other ideas to make this even faster.

This is the updated code:

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int limit, prime, counter;

    cout<<"Introduce a limit: "; cin>>limit;
    cout<<"Prime numbers from 1 to "<<limit<<" are: \n";

    prime = 1; //because 1 is not prime
    counter = 0;

    for(int i = 1; i <= limit; i++)
    {
        prime++;

        for(int j = 2; j <= sqrt(prime);j++)
        {
            if(prime % j == 0) counter++;
        }

        if(counter == 0) cout<< prime <<endl;
        else counter = 0; //If no prime was found, reinitialize counter.
    }

    return 0;
}