Sieve Of Eratosthenes

pIsPrime = true;
for(i=2; i<p; ++i)
  if (p % i == 0) {
    pIsPrime = false;
    break;
  }

pIsPrime = true;
if (p % 2 == 0)
  pIsPrime = false;
 else
   for(i=3; i<p; i+=2)
     if (p % i == 0) {
       pIsPrime = false;
       break;
     }

#include <cmath>
int sqrtP = std::sqrt(p)
  pIsPrime = true;
if (p % 2 == 0)
  pIsPrime = false;
 else
   for(i=3; i<sqrtP; i+=2)
     if (p % i == 0) {
       pIsPrime = false;
       break;
     }

#include <bitset>
ll _sieve_size; // 10^7 should be enough for most cases
bitset<10000010> bs;
vi primes;
void sieve(ll upperbound) {
  _sieve_size = upperbound + 1;
  bs.set(); // all bits set to 1
  bs[0] = bs[1] = 0;
  for (ll i = 2; i <= _sieve_size; i++)
    if (bs[i]) { // cross out multiples of i starting from i * i!
      for (ll j = i * i; j <= _sieve_size; j += i) bs[j] = 0;
      primes.push_back((int)i);
    } }

vi primeFactors(ll N) {
  vi factors;
  ll PF_idx = 0, PF = primes[PF_idx]; // primes has been populated by sie
  while (PF * PF <= N) {
    while (N % PF == 0) {
      N /= PF; factors.push_back(PF); }
    PF = primes[++PF_idx];
  }
  // special case if N is a prime
  if (N != 1) factors.push_back(N);
  return factors;
}