「素数」の編集履歴（バックアップ）一覧はこちら

「素数」(2007/06/26 (火) 20:13:40) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

-単純に素数か否かを判定するアルゴリズム
 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> sieve(int n) {
     vector<int> primes(n);
     for (int i = 2; i < n; ++i)
        primes[i] = i;
        for (int i = 2; i*i < n; ++i)
          if (primes[i])
             for (int j = i*i; j < n; j+=i)
             primes[j] = 0;
     return primes;
 }

-単純に素数か否かを判定するアルゴリズム
 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;
 }














.