专注Java教育14年 全国咨询/投诉热线:444-1124-454
赢咖4LOGO图
始于2009,口口相传的Java黄埔军校
首页 学习攻略 Java学习 Java质数算法介绍

Java质数算法介绍

更新时间:2022-08-05 10:40:24 来源:赢咖4 浏览1097次

Java质数算法是什么?赢咖4小编来为大家解答。质数就是一个数只可以被它自己和1整除(1不是质数)

1.判断一个数是不是质数

只需要让这个数循环除以2到根号n的数 如果出现整除的现象,则不是质数,反之则为质数

源代码:

	public static int F(int x) {   //判断是否为质数 2,3,5,7,11,13,17,19......
		if(x==1) return 0;
		for(int i=2;i<=x/i;i++)
		{
			System.out.println(x+ " "+ i);
			if(x%i==0)
				return 0;
		}
		return 1;
	}

除了判断是否是质数,我们还可以分解质因数

2.分解质因数

根据算术基本定理又称唯一分解定理,对于任何一个合数, 我们都可以用几个质数的幂的乘积来表示。

算法逻辑描述:循环找质因数,找到时循环继续除以这个数,记录个数,直到不整除时退出循环继续找下一个质因数,如果最后n不是1,说明还有最后一个质因数也就是它本身n,输出出来。

源代码:

	public static void prime(int n){
	    for(int i = 2; i <= n / i; i++){      循环到根号n为止
	        int a = 0, b = 0;
	        while(n % i == 0){                如果可以整除说明是质因数
	            a = i;
	            n /= i;                       一直除以这个数直到不整除为止
	            b++;                          累计a的个数
	        }
	        if(b > 0)
	            System.out.println(a + " " + b);
	    }
	    if(n > 1) System.out.println(n + " " + 1);
	}
输入
24
输出
2 3
3 1

3.埃氏筛选法

找出1到100之间的质数的方法可以根据第一种判断质数的方法循环判断100次,还有一种方法就是唉氏筛选法。

算法介绍:先建立一个数组,0表示质数,1表示合数。从2开始找质数,找到一个质数则把2的倍数的数都变成1,然后3开始找质数,把3的倍数的数都变成1…

例如找出1到18之间的质数

先筛选掉2的倍数,4,6,8,10,12,14,16,18,然后筛选掉3的倍数,6,9,12,15,18,然后筛选掉5的倍数,10,15,以此类推循环到18。

	static int st[] = new int [100];        //0表示质数,1表示合数
	static int n;
	public static void E(int n) {
		for(int i=2;i<=n;i++) {
			if(st[i]==0)                    //第一轮,2开始,4,6,8,10,12...20被筛选
			{                               //第二轮,3开始,6,9,12,15,18被筛选
				for(int j=2*i;j<=n;j+=i)    //第三轮,5开始,10,15,20被筛选
					st[j]=1;
				}
		}
	}

 

提交申请后,顾问老师会电话与您沟通安排学习

免费课程推荐 >>
技术文档推荐 >>