求素数java_Java求素数的算法
java求素数的算法由⼴州疯狂软件java培训分享：
只能被1和它⾃⼰本⾝所整除的数成为素数或质数，以下为三种求N以内素数的算法。
⼀、从1⾄N全部遍历，当这个数只能被1和n整除它就是素数。
/**
* 打印⾃然数n以内的素数
*/
public void printPrime(int n){
//是否为质数
boolean isPrime;
for (int i = 1; i <= n; i++) {
isPrime = true;
for (int j = 2; j < i; j++) {
//若能除尽，则不为质数
if ((i % j) == 0) {
isPrime = false;
break;
}
}
//如果是质数，则打印
if (isPrime) {
System.out.println(i);
}
}
}
⼆、筛数法求素数
筛数法求素数的基本思想是：把从1开始的、某⼀范围内的正整数从⼩到⼤顺序排列， 1不是素数，⾸先把它筛掉。剩下的数中选择最⼩的数是素数，然后去掉它的倍数。依次类推，直到筛⼦为空时结束。
public void printPrimes(int n){
//定义arr数组来表⽰筛选出来的素数
boolean arr[] = new boolean[n];
//arr数组坐标i不是素数的话就令arr[i]=false
for(int k=2;k
if(!arr[k]){
for(int i=2*k;i< p>
arr[i] =false;
}
}
}
//把求的素数放⼊数组a中。
for(int i=1;ijava就业课程培训
if(arr[i]){
System.out.println(i);
}
}
}
三、6N±1法求素数
任何⼀个⾃然数，总可以表⽰成为如下的形式之⼀：
6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
显然，当N≥1时，6N，6N+2，6N+3，6N+4都不是素数，只有形如6N+1和6N+5的⾃然数有可能是素数。所以，除了2和3之外，所有的素数都可以表⽰成6N±1的形式(N为⾃然数)。
根据上述分析，我们只对形如6 N±1的⾃然数进⾏筛选，这样就可以⼤⼤减少筛选的次数，从⽽进⼀步提⾼程序的运⾏效率和速度。
以下代码需要⾃然数⼤于10 。
public int[] getPrimes(int n){
int []a = new int[200];
int k=0;
int num = 5;
a[0]=1;a[1]=2;a[2]=3;a[3]=5;a[4]=7;
for(int i=3;i< p>
for(int j=0;j<2;j++){
k = 2*(i+j)-1;
if((k
a[num] = k;
num++;
}
}
}
return a;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。