notebook/code/Primes.cc

// O(sqrt(x)) Exhaustive Primality Test
bool IsPrimeSlow (LL x)
{
  if(x<=1) return false;
  if(x<=3) return true;
  if (!(x%2) || !(x%3)) return false;
  LL s=(LL)(sqrt((double)(x))+EPS);
  for(LL i=5;i<=s;i+=6)
  {
    if (!(x%i) || !(x%(i+2))) return false;
  }
  return true;
}
// sieve
const int maxn = 10000005;
const int maxp = 700000;
int vis[maxn]; //0 for prime number
int prime[maxp];
void sieve(int n){
	int m = (int)sqrt(n+0.5);
	memset(vis, 0, sizeof(vis));
	for (int i = 2; i <= m, i++) if (!vis[i])
		for (int j = i*i; j <= n; j += i) vis[j] = 1;
}
int gen_primes(int n) {
	sieve(n);
	int c = 0;
	for (int i = 2; i <= n; i++) if (!vis[i])
		prime[c++] = i;
	return c;
}
// Primes less than 1000:
//   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  101  103  107  109  113  127  131  137  139  149  151
// 157  163  167  173  179  181  191  193  197  199  211  223
// 227  229  233  239  241  251  257  263  269  271  277  281
// 283  293  307  311  313  317  331  337  347  349  353  359
// 367  373  379  383  389  397  401  409  419  421  431  433
// 439  443  449  457  461  463  467  479  487  491  499  503
// 509  521  523  541  547  557  563  569  571  577  587  593
// 599  601  607  613  617  619  631  641  643  647  653  659
// 661  673  677  683  691  701  709  719  727  733  739  743
// 751  757  761  769  773  787  797  809  811  821  823  827
// 829  839  853  857  859  863  877  881  883  887  907  911
// 919  929  937  941  947  953  967  971  977  983  991  997
// Other primes:
// The largest prime smaller than 10 is 7.
// 100 is 97.
// 1000 is 997.
// 10000 is 9973.
// 100000 is 99991.
// 1000000 is 999983.
// 10000000 is 9999991.
// 100000000 is 99999989.
// 1000000000 is 999999937.
// 10000000000 is 9999999967.
// 100000000000 is 99999999977.
// 1000000000000 is 999999999989.
// 10000000000000 is 9999999999971.
// 100000000000000 is 99999999999973.
// 1000000000000000 is 999999999999989.
// 10000000000000000 is 9999999999999937.
// 100000000000000000 is 99999999999999997.
// 1000000000000000000 is 999999999999999989.