Prime Numbers

[adam2016]

So I've wrote a simple algorithm below to test for prime numbers,
a prime number must only have two divisors itself and 1, so if we loop through all the numbers that come before the number being tested and find that one of the previous numbers modulo the said number == 0 then that number is not prime, if you test the program it works as expected, telling you if a number is prime or not.

This answer on stackoverflow instead of looping through all the numbers -1, loops 2*i < n, essentially doubling the amount of numbers being looped through, so my question is why do they do this? especially when you don't need to?

https://stackoverflow.com/a/17817403/9421071

thanks

  // mycode
  void findPrimes(int number){

      bool notPrime = false;

      for(int i = 2; i < number-1; i++){

         if(number % i == 0){

            notPrime = true;
            break;
         }
      }

      if(!notPrime){
         cout << "prime" << endl;
      }else{

         cout << "not prime" << endl;
      }
}

[dutch]

It doesn't double the loop length, it halves it. Note that i * 2 < n is the same as i < n / 2.
And it's wrong (i.e., inefficient) anyway. It should only go up to the square root.

for (int i = 2; i * i <= n; ++i)

And you can easily only test half as many divisors by testing for 2 separately and only testing odd numbers in the loop.

bool isPrime(int n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0) return false;
    return true;
}

[adam2016]

Thanks dutch, yes you are right my bad on further glance it does indeed half it, but why is this done? why wouldn't they go to n-1 ? like in my example

( why should it only go up to the sqrt )

[dutch]

You only go up to (and including) the square root for efficiency. If no number up to the square root divides evenly then no number above it will either. That's because if a number above the square root divides evenly, like say 20 will divide into 100, then it will have a co-factor below the square root that also divides evenly. In our example, 20 divides 100 five times; since we've already tested 5 we don't need to test 20.

[adam2016]

that makes sense :) thanks Dutch

[SophiaCristina]

even if @dutch replied you, this is my formula if you are curious:
bool IsPrime(long n) { n = abs(n); for (int m = 2; m < n - 1; ++m) { if (0 == n % m) { return(false); } } return(true); }

[nowy20180820]

for (int i = 2; i * i <= n; ++i)

Yes but you will easily get overflow
because there are not infintely many ints like in math

[MikeStgt]

Yes but you will easily get overflow

How about replacing i * i <= n by i <= n / i?

And, BTW, if you use the pre-filters

    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;

you may start your loop from 3 and omit even divisors, instead of i++ "implement" the smallest wheel i += 2. You get other wheels omitting all divisors that are also multiples of 3 and 5. That way you have to test only 8 of 30 numbers to be prime.

And, BTW, why do you use type int instead of unsigned?

And, BTW, what would be wrong using i <= sqrt(n) as loop end test?

[dutch]

nowy wrote:

you will easily get overflow

You will not "easily" get overflow (n needs to be above 2147302921 for 32-bit signed ints), but you are correct that it can overflow and is therefore not a good way of doing it. I usually calculate the sqrt and use that, but MikeStgt has shown how to do it properly without calculating the sqrt.

MikeStqt wrote:

why do you use type int instead of unsigned?

Because the OP used ints.

MikeStqt wrote:

what would be wrong with using i <= sqrt(n) as loop end test?

It would be inefficient to calculate the sqrt every time the loop executes its test. The compiler may optimize the code by moving the sqrt calculation before the loop. But it's best to do that yourself:

int limit = int(sqrt(n));
for (int i = 3; i <= limit; i += 2)

[adam2016]

Hi guys,

I have a follow up, I thought it was concrete but I'm still a little confused

referring to this answer on SO - https://stackoverflow.com/a/5813926/9421071

Let's say m = sqrt(n) then m × m = n. Now if n is not a prime then n can be written as n = a × b, so m × m = a × b. Notice that m is a real number whereas n, a and b are natural numbers.

Not too sure what they mean by this, what do they mean bu saying m is a real number whereas n,a and b are natural numbers?

lets say if m = sqrt(100) then 10 x 10 = 100, so m x m (10 x 10) = a x b, but 10 is a natural number?

thanks

[dutch]

He's just being technical. You're getting (very) confused over nothing. The top answer on that SO page is better.

I say you're getting "very" confused since your example (sqrt(100)) is an extremely bad example of what he's talking about. The point is that the exact sqrt of an integer will not usually be an integer. He goes through the different cases of how a and b (a factorization of n that proves it isn't prime) will relate to the exact sqrt.

[MikeStgt]

natural numbers?

Natural numbers are for counting, one man = one vote, simplest. (Trouble starts with one share = one vote.)
Real numbers comprise also natural numbers, so there is no contradiction in your 10 x 10 = 100 example.

[adam2016]

He's just being technical. You're getting (very) confused over nothing. The top answer on that SO page is better.

I say you're getting "very" confused since your example (sqrt(100)) is an extremely bad example of what he's talking about. The point is that the exact sqrt of an integer will not usually be an integer. He goes through the different cases of how a and b (a factorization of n that proves it isn't prime) will relate to the exact sqrt.

Oh ok I think I get it now, so basically lets say we have 16 the square root of 16 = 4

the factors of 16 are :
4 x 4 = 16
2 x 8 = 16

so lets take the second factor 2 x 8 = 16:
so 16 modulo 2 = 0, this means that it's co-factor 8 in this case will also equal 0 when you do 16 modulo 8, so if one co factor will divide evenly into a number than there is no need to check its co-factor as that co-factor will obviously also go into 100 evenly, right?

so that's why we only need to do it to the square root right?

thanks

[dutch]

Yep, that's it. :)

[adam2016]

thanks dutch