印刷N素数のペア、C++

Question

私は素数のN組の印刷されたプログラムを記述する必要があり、これらのペアは、次のとおり

PQ pおよびqは素数であり、q =いる

p + 2。

入力例：

のn = 3

3 5 // 5 7 // 11 13 //

私はかなりどこにもまだ...だから、誰ですか？ここで

#include <iostream> 
#include <cmath> 

int twins(int n) 
{ 
    for (int i = 0; i < n; i++) 
    { 
     ??? 
    } 
} 

int main() 

{ 
    std::cout<<twins(5); 
    return 0; 
} 

Answer 1

な獣のトップレベルの簡単な擬似コードです：

def printTwinPrimes(count): 
    currNum = 3 
    while count > 0: 
     if isPrime(currNum) and isPrime(currNum + 2): 
      print currnum, currnum + 2 
      count = count - 1 
     currNum = currNum + 2 

我々は4であるため2,4はツインプライムペアとして不可能である知っているので、それは単に（3から始まります複合）。それぞれの可能性について、それはツインプライムペアを構成するかどうかをチェックし、そうであればプリントします。

実数コードに変換する以外に、isPrime()を作成することは、ネット上に無数の例があります。

完全を期すため、ここでは簡単なものでは初心者のための最も効率的なものの、十分な決して、です：

def isPrime(num): 
    if num < 2: 
     return false 
    root = 2 
    while root * root <= num: 
     if num % root == 0: 
      return false 
     root = root + 1 
    return true 

あなたが 2よりもその全ての素数が他の事実を使用して、それがより効率的にすることができますがまたは3つの形式6n±1, n >= 1^（A）である：

def isPrime(num): 
    if num < 2: return false 
    if num == 2 or num == 3: return true 
    if num % 2 == 0 or num % 3 == 0: return false 
    if num % 6 is neither 1 nor 5: return false 

    root = 5 
    adder = 2     # initial adder 2, 5 -> 7 
    while root * root <= num: 
     if num % root == 0: 
      return false 
     root = root + adder  # checks 5, 7, 11, 13, 17, 19, ... 
     adder = 6 - adder  # because alternate 2, 4 to give 6n±1 
    return true 

---

^（A）あなたは6により任意の負でない数を分割し、余りが0,2又は4である場合、それはいても、したがって、非プライム（2ここで、例外ケースである）：

6n + 0 = 2(3n + 0), an even number. 
6n + 2 = 2(3n + 1), an even number. 
6n + 4 = 2(3n + 2), an even number. 

余りが3である場合、それは（3ここで、例外ケースである）3で割り切れるしたがって非素数である：

6n + 3 = 3(2n + 1), a multiple of three. 

だけ余り1及び5を残し、それらの数字は、そのフォームの全てであることを6n±1。

Answer 2

が最も効率的ではないかもしれませんが、あなたはn個まですべての素数を計算することができ、ベクトルに格納し、その後わずか2

#include <iostream> 
#include<vector> 
using namespace std; 

void pr(int n, vector<int>& v) 
{ 
    for (int i=2; i<n; i++) 
    { 
     bool prime=true; 
     for (int j=2; j*j<=i; j++) 
     { 
      if (i % j == 0) 
      { 
       prime=false; 
       break;  
      } 
     } 
     if(prime) v.push_back(i); 
    } 
} 
int main() 
{ 
    vector<int> v; 
    pr(50, v); 
    for(int i = 0;i < v.size()-1; i++) { 
     if(v[i+1]-v[i] == 2) { 
      cout << v[i+1] << " " << v[i] << endl; 
     } 
    } 

    return 0; 
} 

Answer 3

の違いを持っ​​ているものを印刷し、私はあなたのための効率的なアルゴだと思うし、理解しやすい。あなたはあなたの制約に従ってkの値を変えることができます。

#include <iostream> 
#include <cstring> 
using namespace std; 

int n,p=2,savePrime=2,k=100000; 

void printNPrime(int n) 
{ 
    bool prime[k]; 
    memset(prime, true, sizeof(prime)); 

    while(n>0) 
    { 
     if (prime[p] == true) 
     { 
      if(p-savePrime == 2) 
      { 
       cout<<savePrime<<" "<<p<<endl; 
       n--; 
      } 
      // Update all multiples of p 
      for (int i=p*2; i<=k; i += p) 
       prime[i] = false; 
      savePrime=p;  
     } 
     p++; 
    } 

} 

int main() { 
    cin>>n; 
    printNPrime(n); 
    return 0; 
}