-1

ユーザー入力整数をカバーする素数のリストを作成し、そのリストを直線的に検索し、入力整数がそのリストにある場合は true を返す bool Isprime 関数を作成しようとしています。ただし、入力整数をカバーするリストを作成する方法を理解するのに問題があります (つまり、ユーザーが 4 を入力した場合、リストには 2、3、および 5 が含まれている必要があります)。

これが私がこれまでに持っているコードです（完全に間違っていることはわかっています。調査を試みましたが、これを行う方法がわかりません。

bool Isprime(int N){
  int i,tprime=3;
  list<int>prime;
  prime.push_back(2);
  list<int>::iterator it;
    for (it=prime.begin();it!=prime.end();it++){
      if (*it<N){
        while (i<sqrt(tprime)){
          if(N%i!=0){
            if(i<sqrt(tprime))
              i++;
            else prime.push_back(tprime);
          }
        tprime++;
        }
      }
    }
  for (it=prime.begin();it!=prime.end();it++){
    if (*it==N)
      return true;
  }
  return false;
}

これを機能させる方法についてのヒントを教えてもらえますか？線形検索を理解できます。

4

1 に答える 1

0

You got a list of known primes which you can use to check each individual number to see if it a prime. Right now you try to iterate over this list on the outer level. That doesn't seem to be quite right.

Here is one way to go about it (matching what you tried to do):

  1. Count from 3 up to the number you are looking for.
  2. Determine the maximum prime value you need to check against (i.e., the square root of the number)
  3. For each number check if it is a prime number by determining the reminder of dividing it to each element of the known primes list up to the maximum value you need to check.
  4. If the number is a prime, add it to the list of known primes.
于 2013-10-06T16:42:11.913 に答える