C ++ Task with a number from a book

Question

I'm starting with C ++;) How good is the code below as a way of finding all primes between 2-1000:

int i, j; for (i=2; i<1000; i++) { for (j=2; j<=(i/j); j++) { if (! (i%j)) break; if (j > (i/j)) cout << i << " is prime\n"; } } 

Answer 1

One simple answer to all the text that we posted here: Trial division ! If someone mentioned the mathematical basis on which this task is based, we would save a lot of time;)

Answer 2

You stop when j = i. The first simple optimization is to stop when j = sqrt (i) (since there can be no more factors than its square root).

A faster implementation is, for example, a sieve from eratosthenes .

Edit: The code looks a bit cryptic, here's how it works:

The termination condition on the inner for is i/j , equivalent to j<i (which is much clearer), since when there is eventually j==i , we will have i/j==0 , and for will break.

The following if(j>(i/j)) check is really nasty. It basically just checks to see if the loop is in the final condition (so we have a simple one), or if we click on an explicit break (there is no simple one). If we push the end, then j==i+1 (think about it) => i/j==0 => it's simple. If we reach the gap, this means that j is a factor i , but not just any factor that is actually the smallest (since we are leaving the first j that divides i )! Since j is the smallest factor, the other factor (or the product of the remaining factors given by i/j ) will be greater than or equal to j , therefore, the test. If j<=i/j , we get to the gap and j is the smallest factor i .

Something unreadable code!

Answer 3

Not very good. In my humble opinion, indents and spaces are disgusting (no offense). To clear it, follow these steps:

 int i, j; for (i=2; i<1000; i++) { for (j=2; i/j; j++) { if (!(i % j)) break; if (j > i/j) cout << i << " is prime\n"; } } 

This shows an error: if (j > i/j) ... must be outside the inner loop for this to work. In addition, I think the condition i/j more confusing (not to mention slower) than just saying j < i (or even nothing, because as soon as j reaches i , i % j will be 0). After these changes, we have:

 int i, j; for (i=2; i<1000; i++) { for (j=2; j < i; j++) { if (!(i % j)) break; } if (j > i/j) cout << i << " is prime\n"; } 

It works. However, j > i/j confuses me. I can’t even understand why this works (I believe that I can understand it if I spend some time looking like this guy ). Instead, I will write if (j == i) .

What you have done here is called the trial section . The best algorithm is the Sieve of Eratosthenes, as indicated in another answer. A few things to check if you are implementing a sieve of Eratosthenes:

• It should work.
• Do not use division or module. Not that they were “bad” (satisfied, they are usually an order of magnitude slower than addition, subtraction, negation, etc.), but they are not needed, and if they are present, this probably means that implementation isn’t it really effective.
• It should be able to calculate primes less than 10,000,000 in about a second (depending on your hardware, compiler, etc.).

Answer 4

Firstly, your code is short and correct, which is very good for a beginner .; -)

This is what I would do to improve the code:

1) Define variables within loops so that they are not confused with something else. I would also make a parameter or constant a border.

 #define MAX 1000 for(int i=2;i<MAX;i++){ for(int j=2;j<i/j;j++){ if(!(i%j)) break; if(j>(i/j)) cout<<i<<" is prime\n"; } } 

2) I would use the Sieve of Eratosthenes , as suggested by Joey Adams and Mau. Please note that I do not need to record this binding twice, so the two uses will always be identical.

 #define MAX 1000 bool prime[MAX]; memset(prime, sizeof(prime), true); for(int i=4;i<MAX;i+=2) prime[i] = false; prime[1] = false; cout<<2<<" is prime\n"; for(int i=3;i*i<MAX;i+=2) if (prime[i]) { cout<<i<<" is prime\n"; for(int j=i*i;j<MAX;j+=i) prime[j] = false; } 

Ratings are also worth considering. i*i<MAX is much faster than j > i/j , and you also do not need to mark any numbers <i * i because they have already been marked if they are compound. The most important thing is time complexity .

3) If you really want to quickly make this algorithm, you need to optimize its cache. The idea is to first find all the primes <sqrt (MAX) and then use them to find the rest of the primes. Then you can use the same memory block to search for all primes from 1024-2047, say, and then 2048-3071. This means that everything will be stored in the L1 cache. I once measured the acceleration of 12 times using this optimization on a sieve of Eratosthenes.

You can also reduce the use of space in half without storing even numbers, which means you don’t have to do the calculations to work on the new block often.

If you're a beginner, chances are you should just forget about the cache for now.

Answer 5

 #include <stdio.h> #define N 1000 int main() { bool primes[N]; for(int i = 0 ; i < N ; i++) primes[i] = false; primes[2] = true; for(int i = 3 ; i < N ; i+=2) { // Check only odd integers bool isPrime = true; for(int j = i/2 ; j > 2 ; j-=2) { // Check only from largest possible multiple of current number if ( j%2 == 0 ) { j = j-1; } // Check only with previous odd divisors if(!primes[j]) continue; // Check only with previous prime divisors if ( i % j == 0 ) { isPrime = false; break; } } primes[i] = isPrime; } return 0; } 

This is working code. I have also included many of the optimizations mentioned in previous posters. If there are any other optimizations that can be done, it would be informative to know.

Answer 6

This function is more effective to see if a number is prime.

 bool isprime(const unsigned long n) { if (n<2) return false; if (n<4) return true; if (n%2==0) return false; if (n%3==0) return false; unsigned long r = (unsigned long) sqrt(n); r++; for(unsigned long c=6; c<=r; c+=6) { if (n%(c-1)==0) return false; if (n%(c+1)==0) return false; }