-2

所以关键是让程序找到并列出 1 和您输入的数字之间的所有素数。我使用 number_test 作为素数测试的数字，除数和除以的数字。

我不确定出了什么问题，就我而言，它在功能上与此处发布的程序相同：打印从 1 到 100 的素数 并进行一些细微更改（输入一个数字，将“i”更改为小于输入的数字）。

在过去的三四天里，我一直在寻找，但我还没有找到任何能真正完全回答这个问题的东西，达到我上课所需的程度。任何帮助深表感谢。

#include iostream
#include conio.h
using namespace std;

void main(void){
//Declare variables
int number_entered;
//Get inputs    
cout << "This program lists all prime numbers from 1 through a positive number entered."
 << endl;
cout << "Please enter a positive integer."
 << endl;
cin >> number_entered;
cout << "Displaying all numbers from 1 to " << number_entered
 << endl
 << "Press any key to continue..."
 << endl;
getch();

for(int number_test = 2; number_test < number_entered; number_test++){
    for(int divisor = 2; divisor < number_test; divisor++){
        if(number_test % divisor == 0){
            break;
        }
        else if(number_test % divisor != 0){
            cout << number_test << " ";
            break;
        }
    }
}

getch();
}
4

9 回答 9

9

您应该使用埃拉托色尼筛法来计算小于n的素数。首先列出从 2 到最大所需素数n的所有数字。然后，在每个迭代步骤中，输出尚未考虑的最小剩余数，并将其所有倍数从列表中划掉。

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve(p)
            output p
            for i from p*p to n step p
                sieve[i] := False

这个 O(n log log n) 算法非常快；您应该能够在不到一秒的时间内计算出少于一百万个的 78498 个素数。

于 2013-10-18T16:55:51.320 回答
2

只是一个小建议。由于素数是奇数，偶数可以省略。例如，在下面的循环中，i 和 j 增加 2 (i +=2) 而不是 1 (i ++)。

for (int i=3;i<=numberByUser; i+=2){
    for (j=3;j<=i;j +=2){
        if (i%j==0){
            break;
        }
    }
于 2015-01-01T09:34:50.263 回答
2

一个简单的 C++ 程序，用于查找“N”个素数。

    #include  <iostream >
    using  namespace  std;

    int  main()
    {
        int  N;
        cin  >>  N;
        for (int  i =  2;  N > 0;  ++i)
        {
            bool  isPrime  =  true ;
            for (int  j =  2;  j < i;  ++j)
            {
                if (i  % j ==  0)
                {
                    isPrime  =  false ;
                    break ;
                }
            }
            if (isPrime)
            {
                --N;
                cout  <<  i  <<  "\n";
            }
        }
        return  0;
    }
于 2014-05-24T09:42:52.000 回答
1

我认为在你的回答中，一旦循环将终止（我说的是循环检查它是否是素数）一旦它出来你不知道它是否中断了。所以试着做一个标志变量并在外面检查。我认为这会起作用

for(n=lower+1; n<upper; n++)
 {
    prime = 1;
     for(i=2; i<n; i++)
       if(n%i == 0)
         {
          prime = 0;
           break;
          }
       if(prime)
        printf("\n\n\t\t\t%d", n);
 }
于 2013-10-18T16:40:10.273 回答
0

当我的观点和你的观点一样时，我写了这段代码，它奏效了。希望它会帮助你。

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

vector <int> sn;

bool isPrime(int n) {
        if (n <= 1) {
                return 0;
        }
        if (n == 2) {
                return true;
        }
        if (!(n % 2)) {
                return false;
        }
        for (int i = 2; i*i <= n; i++) {
                if (!(n % i)) {
                        return 0;
                }
        }
        return 1;
}

void primeNumbers(int k) {
        sn.push_back (2);
        int i = 3, j = 1;
        for ( ; j < k + 1; i += 2 && j++) {
                if (isPrime(i)) {
                        sn.push_back(i);
                }
        }
}

int main() {
        int i, k;
        scanf("%d", &k);
        primeNumbers(k);
        for (i = 0; i < sn.size(); i++) {
                printf("%d ", sn[i]);
        }
        return 0;
}
于 2013-10-18T16:53:02.263 回答
0 
for(int number_test = 2; number_test < number_entered; number_test++){
    for(int divisor = 2; divisor < number_test; divisor++){
        if(number_test % divisor == 0){
            break;
        }
        else if(number_test % divisor != 0){
            cout << number_test << " ";
            break;
        }
    }
}

上面的代码不会向您显示素数，它只会显示您输入的数字，如果/当您遇到一个不是数字因素的除数时。例如，如果您输入“9”，您将从 2 开始，这不是 9 的因数，因此您会将“9”（错误地）显示为“素数”，而事实并非如此。

测试一个数是否为素数的最简单方法是检查其平方根以下的所有素数，以查看它们是否是给定数的因数。如果它们都不是（那么给定数字以下的非质数都不是），则该数字是质数。如果它至少有一个质因数小于或等于它的平方根，则它不是质数。

由于您希望显示 [0, X] 范围内的所有素数，因此您可以简单地检查您的因子列表（或者反过来进行，这实际上是 Eratosthenes 筛所做的）。

于 2013-10-18T16:32:22.373 回答
0 
int getNumberOfPrimes(int N) {
    bool *numbers = new bool[N-1]();

    for (int i = 2; i <= N/2; ++i) {
        if (numbers[i-2] == true) continue;

        for (int j = i+i; j <= N; j = j+i) {
            numbers[j-2] = true;
        }       
    }

    int count = 0;
    for (int i = 0; i < (N-1); ++i) {
        if (numbers[i] == false) ++count;
    }

    delete []numbers;
    return(count);
}
于 2015-04-26T01:03:48.067 回答
0

伙计，我想我有这一切中最简单的方法。希望这对你有用！

#include < iostream >

using namespace std;

int main()
{
  int n, i, j
  cin>>n;  //The max limith
  for(i=2; i<=2; i++)
   {
     for(j=1; j<=i/2; j++)
      if(i%j!=o)
      cout<<i;
   }

 return 0;
}
于 2018-02-27T15:22:15.790 回答
0

如果一个数有除数，则其中至少一个必须小于或等于该数的平方根。当你检查除数时，你只需要检查到平方根，而不是一直到被测试的数字。

于 2018-03-29T15:50:49.680 回答