求1~n之间的素数
程序员文章站
2022-03-13 09:49:52
...
求1~n之间的素数
前情提要:不知最近为啥爱上了Java,就像阿珍爱上了阿强~~咳咳,回归主线,今天来讲一讲就素数
先画一下划重点:
0和1都不是素数!!
2是最小的素数
知道以上两点哈,我们的初始点就比别人高很多了
废话不多说,直接上代码
package NO1; //记得打包哦,方便管理
import java.util.Scanner;
public class Main5{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
if(n <= 1){
System.out.println("输入n不是大于1正整数");
}
int j;
for (int i = 2; i <= n; i++) // 1不是素数,所以直接从2开始循环
{
j = 2;
while (i % j != 0)
j++; // 测试2至i的数字是否能被i整除,如不能就自加
if (j == i) // 当有被整除的数字时,判断它是不是自身
System.out.print(i+" "); // 如果是就打印出数字
}
}
}
上面的这种方法是不是简单易懂呢?或者说求素数本来就是很简单的一个过程
##当然求素数的方法还有很多种##
比如:
int sq = sqrt(n);
for (int i = 2; i <= sq; i += 2) {//偶数已经判断过了
if (n % i == 0)
return 0;
}//这种算法在时间复杂度上大大减少相对于上面的算法
再比如:
for(int i = 2; i <= n/2;i++){
if (n % i == 0)
return 0;
}//与求根的方法大同小异,但耗费的时间可能会更长
一只初涉Java的小萌新,希望大佬们批评指正~~
上一篇: 给个n,求1到n的所有数的约数个数的和~
下一篇: Python全栈之递归函数