Optimizing prime numbers code?

Question

I wrote this code to show the primes between 1 and 100. The only condition is to do not use functions, whole code should be inline. I would ask if I can improve (optimize) it much more?

#include<iostream>

using namespace std;

int main() {

    int i=2,j=2;

    cout<<"Prime numbers between 1 and 100 are:"<<endl;
    cout<<"2"<<"\t";
    while(i!=100) {
        for(int j=2;j<i;j++) {
            if(i%j==0)
            break;

            if(j==i-1)
            cout<<i<<"\t";
        }

        i++;
    }

    cout<<endl;
    system("pause");
    return 0;
}

Answer 1

    for(int j=2;j<i;j++){

This one is not nice.

First of all, you only need to check for j <= sqrt(i), as for example 7 will never divide 12 without a rest.

Second, you should keep track of all previously found prime numbers; keep it in vector and only do this loop for it's contents and for that condition I wrote.

Answer 2

You could optimise your existing code:

• In the while loop you should have a step of 2, so that you do not test the even numbers.
• In your for loop you should stop when you reach the square root of the number you are testing

You could use a different method:

• Sieve of Erastoses: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

On the Sieve of Erastoses just removing the numbers divisable by 2,3 and 5 would significantly reduce the number of times you need to test for primality.

Answer 3

Avoid using the square root function, and increment your divisor by 2. Also some tricky things in the i loop to increment your possible prime by 2. Inner loop doesn't even need to check divisibility by 2 since no even numbers will even be tested.

int i,j,sq;
int min;
for(sq = 2; sq <= 10; sq++)
{
  min = (sq-1)*(sq-1);
  min = min + (min+1)%2; //skip if it's even, so we always start on odd
  for(i = min; i < sq*sq; i+=2)
  {
    for(j = 3; j <= sq; j+=2)
    {
      if (i%j == 0)
        bad;
    }
  }
}

note that the sq loop doesn't add time because it shrinks the inner loops proportionately.

Answer 4

You are checking every number from 2 to 100. But since 2 is the only even prime number, you can skip every even number after 2. This goes for both i and j. So start i and j at 3, and increment them by 2.

#include<iostream>

using namespace std;

int main() {
    cout<<"Prime numbers between 1 and 100 are:"<<endl;
    cout<<"2"<<"\t";
    for (int i=3; i<100;i+=2) {
        // This loop stops either when j*j>i or when i is divisible by j.
        // The first condition means prime, the second, not prime.
        int j=3;
        for(;j*j<=i && i%j!=0; j+=2); // No loop body

        if (j*j>i) cout << i << "\t";
    }
    cout<<endl;
    return 0;
}

In addition to the trick mentioned above, I've added the condition j*j<=i which logically is the exact same as j<=sqrt(i). There's no need to compute the square root when you can do a simple multiplication.

Answer 5

If you just want primes below 100, there's no need to write code to compute them. It's perhaps a stupid answer, but it solves your problem as stated efficiently and concisely.

int main() {
    cout << "Prime numbers are:" << endl << "2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97" << endl;
    return 0;
}

Answer 6

Depends which optimisation you're looking to do. Yours is as good as possible that I can see if you're optimising for space first, time second (well, close - as long as you listen to @Paul, it will be). If you reverse the priorities, the Sieve of Erastothenes is faster (but will take up 100 booleans of your memory).

Answer 7

Two simple optimizations you could do:

cout << 2 << '\t';
for (int i = 3; i <= 100; ++i) {
    for (int j = 3, l = (int)sqrt(i); j <= l; j += 2) {
        if (i % j == 0) {
            cout << i << '\t';
            break;
        } 
} 

What I did:

Math:

• Stop when j > sqrt(i), there's no need to go further than that. Note however that sqrt is an expensive function; for your small sample (from 1 to 100), it might (read, will surely) cost you more to use it.
• Only check odd numbers; do j += 2 instead of incrementing j one by one

Micro-optimizations:

• Use ++i instead of i++; the latter has a temporary variable in which it stores the original value of i; the former does not.
• Print '\t' as a character not as a string "\t".

(These micro-optimizations are probably made automatically by the compiler anyway, but there's no harm in knowing about them.)

Answer 8

The most efficient way to accomplish this is the Sieve of Eratosthenes. Here's an incremental version, specifically tailored to producing the primes up to 100, one by one (maximum up to 120, because 121 == 11 * 11).

int m3 = 9, m5 = 25, m7 = 49, i = 3;
printf("2 ");
for( ; i < 100; i += 2 )
{
    if( i != m3 && i != m5 && i != m7)
        printf("%d ", i);
    else
    {
        if( i == m3 ) m3 += 6;
        if( i == m5 ) m5 += 10;
        if( i == m7 ) m7 += 14;
    }
}

Answer 9

/*** Return an array of primes from 2 to n. ***/
int[] function nPrimes(int n) {
   int primes[];  //memory allocation may be necessary depending upon language.
   int p = 0;
   bool prime;
   for (int i = 2; i <= n; i++) {
       prime = true;
       //use (j <= (int)sqrt(i)) instead of (j < i) for cost savings.
       for (int j = 2; j <= (int)sqrt(i); j++)  {
           if (i % j == 0) {
               prime = false;
               break;
           }
       }
       if (prime) {
           primes[p++] = i;
       }    
   }
   return primes;
}