java 编写一种求素数的方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16682939/
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
Writing a method to find prime numbers
提问by Jessica M.
I'm trying to write a program that uses a predicate method that finds all the prime numbers between 1-100. I know there are more efficient ways of finding prime numbers but right now but I want to use the brute-force strategy and try every possible combination.
Right now the program as it is, just prints true or false 10,000 times but I want my program to only print the numbers if they are prime. So after the program is done I'll have a list of prime numbers between 1- 100.
1. Is my program correct for what I'm trying to do? 2. What would be good suggesting to change my program so that it lists all the prime numbers between 1-100.
我正在尝试编写一个程序，该程序使用谓词方法查找 1-100 之间的所有素数。我知道有更有效的方法可以找到质数，但现在我想使用蛮力策略并尝试所有可能的组合。
现在的程序，只是打印真或假 10,000 次，但我希望我的程序只打印质数的数字。所以在程序完成后，我会得到一个 1-100 之间的素数列表。
1. 我的程序是否适合我想要做的事情？2. 建议更改我的程序以便它列出 1-100 之间的所有质数有什么好处。
import acm.program.*;
public class PrimeNumbers extends ConsoleProgram{
public void run(){
for (int i =1; i <= 100, i++){
for (int j =1; j<= 100; j++){
println(yesPrime(i, j));
}
}
}
private boolean yesPrime (int n, int k){
return ( n % k == 0)
}
}
}
回答by John
You're not checking for primes. You're testing all 10,000 combinations of two numbers from 1 to 100 to see if the second divides the first evenly.
你不是在检查素数。您正在测试从 1 到 100 的两个数字的所有 10,000 种组合，以查看第二个数字是否将第一个数字整除。
But it's likely doing that correctly.
但这很可能是正确的。
Pseudocode for what you want to do:
你想要做的伪代码：
for each number n from 2:100
for each divisor d from 2:n-1
test to see if d divided n evenly
end for
if no values of d other than n divided n evenly
print "n is prime"
end for
A couple of optimizations for you to ponder:
一些优化供您思考：
- Your inner loop only has to go up to sqrt(n). (Why?)
- Instead of all numbers, you only need to check to see if it divides the odd primes you've already found evenly. (Why?)
- 您的内部循环只需要上升到 sqrt(n)。（为什么？）
- 您只需要检查它是否将您已经找到的奇素数整除，而不是所有数字。（为什么？）
Have fun!
玩得开心！
回答by Paul Vargas
Using the sieve of Eratosthenes:
使用埃拉托色尼筛法：
public static void main(String[] args) {
int n = 100; // the max number for test
// Sieve of Eratosthenes
boolean[] sieve = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
sieve[i] = true;
}
for (int i = 2; i <= n; i++) {
if (sieve[i] != false) {
for (int j = i; j * i <= n; j++) {
sieve[i * j] = false;
}
}
}
// Print prime numbers
for (int i = 0; i <= n; i++) {
if (sieve[i]) {
System.out.println(i);
}
}
}
回答by Achrome
Well, you are returning a comparison from yesPrime, and then printing the result of that comparison in run. Guess what the output would be.
好吧，您正在从 返回一个比较yesPrime，然后在 中打印该比较的结果run。猜猜输出会是什么。
Taking that this is an assignment, I would like to give you a hint instead of the answer.
考虑到这是一个作业，我想给你一个提示而不是答案。
Check the result of yesPrime. If true, print the number and break out of the loop.
检查 的结果yesPrime。如果为真，则打印数字并跳出循环。
回答by Apurva Sharma
Scanner reader = new Scanner(System.in);
System.out.println("Enter the a number");
int num = reader.nextInt();
int counter = 0;
int root = 0;
boolean prime_flag;
if (2 <= num) {
// 2 is the only even prime number
counter++;
}
for (int i = 3; i < (num + 1); i++) {
// test only for odd number
if (i % 2 != 0) {
prime_flag = true;
root = (int) (Math.sqrt(i) + 1);
for (int j = 3; j < (root + 1); j++) {
if ((i % j == 0) && (i != j)) {
prime_flag = false;
break;
}
}
if (prime_flag) {
counter++;
}
}
}
System.out.println("Count of prime numbers upto " + num + " is "
+ counter);
回答by Valentin Genevrais
With a less complex method we can do this:
使用不太复杂的方法，我们可以做到这一点：
import java.math.BigInteger;
public class PrimeNumbers {
public static void main(String[] args) {
BigInteger min = new BigInteger("2");
BigInteger max = new BigInteger("100");
while(min.compareTo(max) < 0){
System.out.println(min);
min = min.nextProbablePrime();
}
}
}
回答by Vadim Karavayev
Here is my solution for finding primes numbers.
这是我寻找素数的解决方案。
public class PrimeNumberFinder {
public boolean isPrime(int number) {
return number > 1 && IntStream.rangeClosed(2, number / 2)
.noneMatch(value -> number % value == 0);
}
}
回答by Wayne Uroda
I would make a function, something like your yesPrimefunction. This would take one number only, and check to see if that number is prime.
我会做一个函数，就像你的yesPrime函数一样。这将只需要一个数字，并检查该数字是否为质数。
Something like
就像是
boolean yesPrime(int n)
{
// check to see if n is divisble by numbers between 2 and sqrt(n)
// if the number is divisible, it is not prime, so return false
// after the loop has checked all numbers up to sqrt(n), n must be prime so return true
}
Then in your main program, loop over the numbers 1 to 100 and call yesPrime for each number. If the result is true, print that number.
然后在您的主程序中，遍历数字 1 到 100 并为每个数字调用 yesPrime。如果结果为真，则打印该数字。
My reaoning is that one goal of programming is to break problems up into smaller sub-problems. By writing a function to test for prime, you can avoid using nested loops in one function which could be harder to understand.
我的想法是编程的一个目标是将问题分解为更小的子问题。通过编写一个函数来测试素数，您可以避免在一个更难理解的函数中使用嵌套循环。
回答by Adarsh
For starters, you need to check for prime numbers starting from 2. And you do not check it against all the 100 numbers, just every number as a factor starting from 2 till (number-1).Every number is divisible by 1 and itself.
对于初学者，您需要检查从 2 开始的素数。并且您不检查所有 100 个数字，只是将每个数字作为从 2 到 (number-1) 开始的因子进行检查。每个数字都可以被 1 和它本身整除.
public static void main(String[] args) {
boolean b;
for (int i = 2; i < 100; i++) {
b = checkPrime(i);
if (b)
System.out.println(i);
}
}
private static boolean checkPrime(int k) {
for (int i = 2; i < k; i++) {
//check if the number is divisible by any number starting from 2 till number -1.If it is, it is not a prime number
if (k % i == 0)
return false;
}
// return true if the number is not divisible by any number from 2 to number -1 i.e. it s a prime number.
return true;
}
回答by gispyDangre
Just think about this logic
All number divisible by 2 is not prime so you can increment your number by 2
if a number is not divisible by a prime number then it is a prime number
想想这个逻辑
所有能被 2 整除的数都不是素数，所以
如果一个数不能被素数整除，你可以把你的数加 2
，那么它就是素数
try this code
试试这个代码
public static void main(String[] args) throws IOException
{
int[] prime=new int[50]; //array to store prime numbers| within 1 to ==> prime numbers will be <=n/2 here n=100
int i=1; //index for "num" array
int j=1; //index for storing to "prime" array
int k=1; //index for browsing through prime array
prime[0]=2; // setting the first element
int flag=1; // to check if a number is divisibe for than 2 times
for(i=3;i<=100;i+=2) {
for(k=0;prime[k]!=0;k++) //browsing through the array to till non zero number is encountered
{
if(i%prime[k]==0) flag++; //checking if the number is divisible, if so the flag is incremented
}
if(flag<2)
{
prime[j++]=i; // if the flag is still 1 then the number is a prime number
}
flag=1;
}
System.out.println(Arrays.toString(prime)); //a short way to print an array
}
回答by streethawk
find prime numbers easy in a given range /* Please implement this method to return a list of all prime numbers in the given range (inclusively). A prime number is a natural number that has exactly two distinct natural number divisors, which are 1 and the prime number itself. The first prime numbers are: 2, 3, 5, 7, 11, 13 */
在给定范围内轻松找到素数 /* 请实现此方法以返回给定范围内（包括）所有素数的列表。素数是一个自然数，它恰好有两个不同的自然数除数，即 1 和素数本身。第一个素数是：2, 3, 5, 7, 11, 13 */
public void getPrimeNumbers(int st, int en){
// int st=1, en=100;
for(int i=st;i<=en;i++)
if( (i%2!=0) && (i%1==0 && i%i==0) )
System.out.println("Yes prime");
}
