素数 - Programming @ wiki

• 単純に素数か否かを判定するアルゴリズム

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

• エラトステネスの篩

vector<int> Eratosthenes(int n) {
    vector<int> prime(n);
    for (int i = 2; i < n; ++i)
       prime[i] = i;
       for (int i = 2; i*i < n; ++i)
         if (prime[i])
            for (int j = i*i; j < n; j+=i)
            prime[j] = 0;
    return prime;
}

.