java 使用模运算符获取质数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17817089/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Use Modulus Operator to Get Prime Numbers
提问by c12
How would you modify the below to print out all prime numbers from 1-100? The below has an issue with the number 2 coming back as not prime. The if(i%number == 0) condition is met for the number 2 as 2%2 is returned as 0.
您将如何修改以下内容以打印出 1-100 之间的所有质数？下面的问题是数字 2 不是素数。数字 2 满足 if(i%number == 0) 条件，因为 2%2 返回为 0。
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
for(int i=1; i<=100; i++){
if(isPrime(i)){
System.out.println(i + " is a prime number");
}else{
System.out.println(i + " is not a prime number");
}
}
}
public static boolean isPrime(int number){
for(int i=2; i<=number; i++){
if(i%number == 0){
return false;
}else{
return true;
}
}
return false;
}
}
回答by SLaks
i<=number
You shouldn't be checking whether the number is divisible by itself.
您不应该检查数字是否可以被自身整除。
You also have another problem:
你还有另一个问题：
}else{
return true;
}
You're returning true as soon as you find a single non-divisible number, even if it does have factors later.
一旦你找到一个不可整除的数字，你就会返回 true ，即使它以后确实有因数。
回答by Gilbert Le Blanc
Here is an algorithm for determining whether or not a number is prime.
这是一个确定一个数是否为素数的算法。
- Is the number less than 2? If so, return false.
- Is the number 2 or 3? If so, return true.
- Is the number 4? If so, return false.
- Take the square root of the number, rounded up to the next integer. This is optional for small prime numbers, but speeds up the determination for larger numbers.
- Loop from 2 to the square root of the number (or the number), incrementing by 1.
- Divide the loop number by the prime numbers determined so far.
- If the modulus of the division is zero, return false.
- If the loop is completed, return true.
- 数字小于 2 吗？如果是，则返回 false。
- 数字是2还是3？如果是，则返回 true。
- 数字是4吗？如果是，则返回 false。
- 取数字的平方根，四舍五入到下一个整数。这对于小素数是可选的，但可以加快对较大数的确定。
- 从 2 循环到数字（或数字）的平方根，递增 1。
- 将循环数除以目前确定的素数。
- 如果除法的模数为零，则返回 false。
- 如果循环完成，则返回 true。
回答by null
This will work. 2 is a special case when testing for primes. If you start to search a larger and larger...you might want to look at the sieve of eratosphenes.
这将起作用。2 是测试素数时的特殊情况。如果您开始搜索越来越大的内容……您可能想看看埃拉托斯芬的筛子。
Every prime number is a multiple of another number. Take 3 for example. Using the sieve, if you find 3 to be prime it will then 'ignore' all multiples of 3 thus reducing the amount of time taken to find consequent primes. It speeds things up...ALOT :)
每个质数都是另一个数的倍数。以3为例。使用筛选器，如果您发现 3 是素数，它将“忽略”所有 3 的倍数，从而减少查找后续素数所需的时间。它加快了速度......很多:)
public class JavaApplication47 {
public static void main(String[] args) {
for(int i=1; i<=100; i++){
if(isPrime(i)){
System.out.println(i + " is a prime number");
}else{
// System.out.println(i + " is not a prime number");
}
}
}
public static boolean isPrime(int n) {
for(int i=2; 2*i<n; i++) {
if(n%i==0)
return false;
}
return true;
}
}
SIEVE EXAMPLE - NOT IMPLEMENTED - Can be used for reference and understanding.
筛子示例 - 未实施 - 可用于参考和理解。
static boolean [] allPrimes = new boolean[10000];
public static void fillTheSieve(){
Arrays.fill(allPrimes, true);
allPrimes[0] = allPrimes[1] = false; //1 and 0 are false. winning
for (int i = 2; i < allPrimes.length; i++) {
//check if prime, if so getmultiples and declae false
if(allPrimes[i]){
for (int j = 2; i*j<allPrimes.length; j++) {
allPrimes[i*j] = false;
}
}
}
}
回答by Slater Victoroff
You've got a couple issues here. Firstly, when checking whether or not a number is prime, never check every number up to the actual number being checked for primality. A check of all primes up to the square root of the number will always be sufficient.
你在这里有几个问题。首先，在检查一个数是否为素数时，永远不要检查每个数直到被检查素数的实际数。检查所有素数直到数字的平方根总是足够的。
To fix that error look at your for loop condition and edit it accordingly:
要修复该错误，请查看您的 for 循环条件并相应地对其进行编辑：
for(int i=2; i<=number; i++)
Secondly, when a function returns it stops. Currently with your if/else statement:
其次，当函数返回时，它会停止。目前与您的 if/else 语句：
if (i%number == 0) {
return false;
} else {
return true;
}
If this condition goes to the else statement even once it will return true, you want to make sure you only actually return true when you've checked allof the numbers you intend to.
如果这个条件进入 else 语句，即使它会返回 true，您要确保只有在您检查了所有想要的数字后才真正返回 true 。
Additionally I don't think you've carefully considered what you base case is. What you are saying with your last line is that if everything previously slipped through the cracks then it should assume the number isn't prime. Think about it and I'm sure you'll be able to figure it out.
此外，我认为您没有仔细考虑您的基本情况。你在最后一行中所说的是，如果之前所有的东西都从裂缝中溜走，那么它应该假设这个数字不是质数。仔细想想，我相信你会明白的。
回答by Edwin Buck
The definition of a prime numberspecifically states that one cannot be a prime number.
素数的定义明确指出一个人不能是素数。
That means that isPrime(1)should return false. Which your implementation does.
这意味着isPrime(1)应该返回false。您的实现是做什么的。
But isPrime(2)should return true. Which your implementation does not. It does not because (2 % 2 == 0)and you are checking all numbers from 2 to N, not from 2 to N-1. The last number, N, will always yield a zero remainder (N % N == 0)
但isPrime(2)应该返回true。您的实现没有。这不是因为(2 % 2 == 0)您正在检查从 2 到 N 的所有数字，而不是从 2 到 N-1。最后一个数字 N 将始终产生零余数(N % N == 0)
回答by chancea
Just a few things to think about when dealing with Primes. You can have a special case for 2 at the start (i.e. something like if(number == 2)...).
与 Prime 打交道时需要考虑的几件事。您可以在开始时为 2 设置一个特殊情况（即类似if(number == 2)...）。
In addition to your error in checking all the way to i<=numberconsider only how far you need to go in order to be certain it is not prime, hints have already been given with i*ior Math.sqrt
除了你在检查过程中 i<=number只考虑你需要走多远才能确定它不是素数的错误之外，已经给出了提示i*i或Math.sqrt
Another thing in the increment i++think about what that entails, I realize this is only for the first 100 primes but you should always be thinking about performance. Do you really have to check all numbers (2,3,4,5,6...) (hint: if you have checked if its divisible by 2 then you dont need to check for 4,6,8 etc..)
增量中的另一件事是i++考虑这意味着什么，我意识到这仅适用于前 100 个素数，但您应该始终考虑性能。你真的需要检查所有的数字吗（2,3,4,5,6...）（提示：如果你检查过它是否可以被 2 整除，那么你不需要检查 4,6,8 等等。）
Finally with your return statements, consider using a booleanflag that you set to false/true only when you are positivethe number is a prime or is not. And you only need to use 1 return statement.
最后，您return语句，可以考虑使用一个boolean标志，你设置为false /真只有当你正数是素或不是。并且您只需要使用 1 个 return 语句。
Hope that helps.
希望有帮助。
回答by seanxiaoxiao
Please try this
请试试这个
public static boolean isPrime(int number) {
for(int i = 2; i * i <= number; i++) {
if (i % number == 0) {
return false;
} else {
return true;
}
}
return true;
}
