please help me to count prime number between 0 to 100000000 because I use to write but it works very slowly:
Here is my code:
$n =100000000;
$answer =0;
for ($i = 2, $j = 2; $i <= $n; $i++) {
for ($j = 2; $j < $i; $j++) {
if ($i % $j == 0) {
break;
}
}
if ($j == $i) {
$answer++;
}
}
echo $answer . PHP_EOL;
Check out Sieve of Eratosthenes. This problem can be solved in less than 2 seconds on a modern desktop. You can also try Bitwise Sieve which performs better in term of memory and speed.
Change the algorithm. Using Euler sieve.
this is my C++ code. It will only cost 3 or 4 seconds.
bool isprm[100000000+10];
int prm[5000000];
clr(isprm, true);
int cnt = 0;
for(int i=2; i<=n; i++)
{
if(isprm[i]) prm[++cnt] = i;
for(int j=1; j<=cnt && LL(i)*prm[j]<=n; j++)
{
isprm[ i*prm[j] ] = false;
if(i % prm[j] == 0) break;
}
}
skipping even numbers greater 2 and stopping at square root of i should give some speed up
my c code:
int max = 100000000;
int i, j;
int answer = 0;
for(i=2;i<max;i++) {
if(i%2 == 0) continue;
for(j=3;j*j<i;j+=2) {
if(i%j == 0) break;
}
if(j*j >= i) answer++;
}
As mentioned before use Sieve of Eratosthenes
[4929.114 ms] find primes <= 100000000 found 5761456 primesthis is the source in C++:
//---------------------------------------------------------------------------
int primes_found=0;
void addprime(int p)
{
// here do the stuff you want to do with prime p=2,3,5,7,...
// I just count the primes found ...
primes_found++;
}
//---------------------------------------------------------------------------
void getprimes(int p) // compute all primes up to p
{
// sieves N/16 bytes
// ------------------------------
// 0 1 2 3 4 5 6 7 bit
// ------------------------------
// 1 3 5 7 9 11 13 15 +-> +2
// 17 19 21 23 25 27 29 31 |
// 33 35 37 39 41 43 45 47 V +16
// ------------------------------
int N=(p|15),M=(N>>4)+1; // store only odd values 1,3,5,7,... each bit ...
char *m=new char[M]; // m[i] -> is 1+i+i prime? (factors map)
int i,j,k;
// init sieves
m[0]=254; for (i=1;i<M;i++) m[i]=255;
for(i=3;i<=N;i+=2)
for(k=i+i,j=i+k;j<=N;j+=k)
m[j>>4]&=255-(1<<((j>>1)&7));
// compute primes
addprime(2);
for(i=1,j=i>>4;j<M;i+=16,j++)
{
k=m[j];
if (!k) continue;
if (int(k& 1)!=0) addprime(i );
if (int(k& 2)!=0) addprime(i+ 2);
if (int(k& 4)!=0) addprime(i+ 4);
if (int(k& 8)!=0) addprime(i+ 6);
if (int(k& 16)!=0) addprime(i+ 8);
if (int(k& 32)!=0) addprime(i+10);
if (int(k& 64)!=0) addprime(i+12);
if (int(k&128)!=0) addprime(i+14);
}
delete[] m;
}
//---------------------------------------------------------------------------
#define addprime(prime) {...} instead of functionusage:
getprimes(100000000);
[Notes]
[edit1] init sieves by primes only
// init sieves
m[0]=254; for (i=1;i<M;i++) m[i]=255;
for(i=1;i<=N;) // here could be also sqrt(N) instead of N (or half the bits number)
{
int a=m[i>>4];
if (int(a& 1)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;
if (int(a& 2)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;
if (int(a& 4)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;
if (int(a& 8)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;
if (int(a& 16)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;
if (int(a& 32)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;
if (int(a& 64)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;
if (int(a&128)!=0) for(k=i+i,j=i+k;j<=N;j+=k) m[j>>4]&=255-(1<<((j>>1)&7)); i+=2;
}
[1520.160 ms] find primes <= 100000000 found 5761456 primes