A problem about prime number

[wij]

I just wrote a short c++ program to test prime numbers. The program 
indicates that if n (n<=2^32) is a prime then n%30 is also a prime !!!
I think I should have made some mistake but have no idea what. Can
anybody find some thing for me, thanks.

//-------------------------------------------
#include <Wy.stdio.h>
#include "PrimeTab.h"

using namespace Wy;

void ck() {
size_t cnt;
PrimeTab ptab(1LL<<32);
cnt=0;
for(size_t n=0; n<ptab.max_num(); ++n) {
if(ptab.is_prime(n)) {
++cnt;
PrimeTab::NumType n2= n%30;
if(ptab.is_prime(n2)==false) {
cout << n << ' ' << n2 << WY_ENDL;
}
}
}
cout << "cnt=" << cnt << WY_ENDL;
};

int main() {
//...
ck();
return 0;
};

[Ben Bacarisse]

wij <wyni...@gmail.com> writes:

> I just wrote a short c++ program to test prime numbers. The program 
> indicates that if n (n<=2^32) is a prime then n%30 is also a prime !!!
> I think I should have made some mistake but have no idea what. Can
> anybody find some thing for me, thanks.

We're missing the key part of the program.

> //-------------------------------------------
> #include <Wy.stdio.h>
> #include "PrimeTab.h"

Without knowing what's in here (and any other files linked to the code
you show), how can we tell?

> using namespace Wy;
>
> void ck() {
> size_t cnt;
> PrimeTab ptab(1LL<<32);
> cnt=0;
> for(size_t n=0; n<ptab.max_num(); ++n) {
> if(ptab.is_prime(n)) {
> ++cnt;
> PrimeTab::NumType n2= n%30;
> if(ptab.is_prime(n2)==false) {
> cout << n << ' ' << n2 << WY_ENDL;
> }
> }
> }
> cout << "cnt=" << cnt << WY_ENDL;
> };

See below.

> int main() {
> //...
> ck();
> return 0;
> };

It's odd to put ; after a function definition. It's a syntax error in C
but C++ does allow it. None the less, odd.

--
Ben.

[immibis]

If you multiply consecutive prime numbers starting from 2, to get a
number like 2x3x5==30, and then look at prime numbers modulo 30 you see
there are only certain possible values.

Since 30 is a multiple of 2, n%2 == (n-30*k)%2.
By choosing k so that (n-30*k)==n%30 we know n%2==(n%30)%2.
Ditto for 3 and 5.
So if n isn't divisible by 2 or 3 or 5, n%30 still isn't divisible by 2
or 3 or 5.

Here are the numbers less than 30 that aren't divisible by 2, 3 or 5:
1, 7, 11, 13, 17, 19, 23, 29

As you can see they are all prime! ... except for 1. And some prime
numbers mod 30 are 1, such as 31. It's only always prime if you count 1
as prime.

That's because all the numbers less than 30 are either divisible by 2, 3
or 5, or they are prime. The first non-prime number that isn't divisible
by one of those is 49, which is 7x7.



Why only 30? What happens if we try a different modulus? Instead of mod
2x3x5 we can try mod 2x3 or mod 2x3x5x7.

If you take away 5 and try mod 6 (2x3) it works: all prime numbers mod 6
are either 1, or 5 (which is prime).

If you also take away 3 and try mod 2 it almost works, since 2%2==0. But
that's the only exception - all other primes mod 2 are 1.

If you try adding more primes and try mod 210 (2x3x5x7) it doesn't work.
It still works that all the mods aren't divisible by 2, 3, 5 or 7 (and
that will keep working as you add more primes - any primes, not just
consecutive ones) but it doesn't work that those are the only prime
numbers. 121 (11x11) is a number less than 210 which isn't divisible by
2, 3, 5 or 7.
541 is a prime number and 541%210==121.

2x3x5==30 is the only sweet spot where all the numbers less than 30 that
aren't divisible by 2, 3, or 5 are prime (or 1).

What if we skip over some, e.g. do 3x5 instead of 2x3x5? Well then the
numbers that aren't divisible by them aren't all prime, either. E.g. 14
isn't divisible by 3 or 5, but it's less than 15 and not prime. 29 is a
prime and 29%15==14.