素数関連

// ある数字が素数かどうか調べたいとき
// http://www.wolframalpha.com/
// にて数字を入力すると因数分解した結果がでるのでわかる。
// ｢next prime of 100000000｣や「previous prime of 100000000」もできる。


// 素数を調べる
long long isPrime(long long n){
  long long i;
  if(n < 2LL){
    return 0LL;
  }
  else if(n == 2LL){
    return 1LL;
  }
  if(n % 2LL == 0LL){
    return 0LL;
  }
  for(i = 3LL; i * i <= n; i += 2LL){
    if(n % i == 0LL){
      return 0LL;
    }
  }
  return 1LL;
}

// エラトステネスの篩
long long prime[1000];
long long isPrime[1001];

long long sieve(long long n){
  long long p = 0;
  for(long long i = 0; i <= n; i++){
    isPrime[i] = 1LL;
  }
  isPrime[0] = 0;
  isPrime[1] = 0;
  for(long long i = 2LL; i <= n; i++){
    if(isPrime[i] == 1LL){
      prime[p] = i;
      p++;
      for(long long j = 2LL * i; j <= n; j += i){
        isPrime[j] = 0;
      }
    }
  }
  return p;
}