C ++主数字程序 [英] C++ Prime Numbers program
问题描述
我正在使用一个C ++程序，确定并打印3和用户输入的整数'x'之间的素数。我假设我需要一个双嵌套循环，一个从3到x迭代，另一个检查数字是否为素数。我认为它需要做一些事情，从2到x-1？我只是真的不知道如何做这个语法明智。感谢任何帮助！ ：）
I'm working on a C++ program that determines and prints the prime numbers between 3 and an integer 'x' the user inputs. I'm assuming that I need a double nested loop for this, one to iterate from 3 to x and the other to check if the number is prime. I think it needs to do something like go from 2 to x-1? I'm just really not sure how to do this syntax-wise. Thanks for any help! :)
编辑：
这是我所拥有的：
This is what I have:
#include <iostream>
#include <cmath>
using std::cout;
using std::endl;
using std::cin;
int main(){
int x;
int i;
int j;
cout << "Please enter an integer 'x' greater than 3: " << endl;
cin >> x;
if (x <= 3){
cout << "Please enter new value 'x' greater than 3: " << endl;
cin >> x;
}
for(int i=3; i<=x; i++){
for(j=2; j<i; j++){
if(i%j == 0)
break;
else if(i == j+1);
cout << i << endl;
}
}
return 0;
}
当我输入10作为'x'时，我得到输出：
3
5
5
5
7
7
7
7
7
9
And I when I enter 10 as 'x' I get the output: 3 5 5 5 7 7 7 7 7 9
任何人都可以告诉我如何解决这个问题？
Can anyone tell me how to fix this?
推荐答案
X 足够小，您可以使用Sieve of Eratosthenes更有效地做。这对于primes up to X情况是理想的，因为它维护了先前丢弃的素数的存储器。它通过为每个候选数字保持一组标志，所有的初始设置为真（除了1，当然除外）。
Provided your X is small enough, you can use the Sieve of Eratosthenes to do it more efficiently. This is ideal for the "primes up to X" case since it maintains a memory of previously discarded primes. It does so by keeping a set of flags for each candidate number, all initially set to true (except for 1, of course).
然后你取第一个真值（2），输出作为素数，然后将其所有倍数的标志设置为假。
Then you take the first true value (2), output that as a prime, and then set the flags for all multiples of that to false.
然后继续：
- 3;
- 5（因为4是2的倍数）;
- 7（因为6是2和3的倍数）;
- 11（因为8和10是2的倍数，9是3的倍数）;
- 13（因为12是2的倍数）;
- 17（因为14和16是2的倍数，15是3和5的倍数） >
- 等。
- 3;
- 5 (since 4 was a multiple of 2);
- 7 (since 6 was a multiple of 2 and 3);
- 11 (since 8 and 10 were multiples of 2 and 9 was a multiple of 3);
- 13 (since 12 was a multiple of 2);
- 17 (since 14 and 16 were multiples of 2 and 15 was a multiple of 3 and 5);
- and so on.
伪代码类似于：
def showPrimesUpTo (num):
// create array of all true values
array isPrime[2..num] = true
// start with 2 and go until finished
currNum = 2
while currNum <= num:
// if prime, output it
if isPrime[currNum]:
output currNum
// also flag all multiples as nonprime
clearNum = currNum * 2
while clearNum <= num:
isprime[clearNum] = false
clearNum = clearNum + currNum
// advance to next candidate
currNum = currNum + 1
否则，你可以根据你的建议进行试分。基本思想是检查每个数字从2到目标数字的平方根，看看它是否是一个倍数。在伪代码中，这将是：
Otherwise, you can do trial division as per your suggestion. The basic idea is to check each number from 2 up to the square root of your target number to see if it's a multiple. In pseudo-code, that would be something like:
def isPrime (num):
// val is the value to check for factor
val = 2
// only need to check so far
while val * val <= num:
// check if an exact multiple
if int (num / val) * val == num:
return false
// no, carry on
val = val + 1
// if no factors found, it is a prime
return true
你只需要检查平方根的原因是因为，如果你发现一个因素高于那里，你会发现
The reason you only need to check up to the square root is because, if you find a factor above there, you would have already found the corresponding factor below the square root.
例如， 3 x 17 51 。如果你检查从2到50的数字，看看 51 是否是素数，你会发现 3 ，这意味着您从不需要检查 17 。
For example, 3 x 17 is 51. If you're checking the numbers from 2 through 50 to see if 51 is prime, you'll find 3 first, meaning you never need to check 17.
这篇关于C ++主数字程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
