开发者社区> 算精通> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

素数是个什么东西 prime number

简介: /**  * *********************************************************************  * 只有1和它本身两个正因数的自然数,叫质数(Prime Number)。  * (如:由2÷1=2,2÷2=1,可知2的因数只有1和它本身2这两个约数,所以2就是质数。  * 与之相对立的是合数:“除了1和它本身两个因
+关注继续查看



/**
 * *********************************************************************
 * 只有1和它本身两个正因数的自然数,叫质数(Prime Number)。
 * (如:由2÷1=2,2÷2=1,可知2的因数只有1和它本身2这两个约数,所以2就是质数。
 * 与之相对立的是合数:“除了1和它本身两个因数外,还有其它因数的数,叫合数。”
 * 如:4÷1=4,4÷2=2,4÷4=1,很显然,4的因数除了1和它本身4这两个因数以外,还有因数2,所以4是合数。)
 * 100以内的质数有2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
 * 73,79,83,89,97,在100内共有25个质数。
 * 注:(1)2和3是所有素数中唯一两个连着的数。
 * (2)2是唯一一个为偶数(双数)的质数。[1]
 * 质数的平方数只有三个因数.
 * ********************************************************************
 * @param args
 * 题目:判断101-200之间有多少个素数,并输出所有素数。
 */


http://baike.baidu.com/link?url=8QA3pGULdreLhTqpdXcyQpSK7MNXqB4FBWA5DN7an2Ic67mGVycJHUcqRAYtdz4yL2V9T7Qq9glfmNGrOEkbx_


import java.util.ArrayList;
import java.util.Scanner;

public class PrimeNumber {
/**
 * *********************************************************************
 * 只有1和它本身两个正因数的自然数,叫质数(Prime Number)。
 * (如:由2÷1=2,2÷2=1,可知2的因数只有1和它本身2这两个约数,所以2就是质数。
 * 与之相对立的是合数:“除了1和它本身两个因数外,还有其它因数的数,叫合数。”
 * 如:4÷1=4,4÷2=2,4÷4=1,很显然,4的因数除了1和它本身4这两个因数以外,还有因数2,所以4是合数。)
 * 100以内的质数有2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
 * 73,79,83,89,97,在100内共有25个质数。
 * 注:(1)2和3是所有素数中唯一两个连着的数。
 * (2)2是唯一一个为偶数(双数)的质数。[1]
 * 质数的平方数只有三个因数.
 * ********************************************************************
 * @param args
 * 题目:判断101-200之间有多少个素数,并输出所有素数。
 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//根据输入的两个数,输出两数之间的全部素数
		int start = 0, end = 0;
		Scanner input = new Scanner(System.in);
		System.out.println(" 请输入大于1的两个数区间 ");
		while(start <= 1 || end <= 1){
			try{
			start = input.nextInt();
			end = input.nextInt();
			}catch(Exception e){}
		}
		input.close();
		
		ArrayList list = new ArrayList();//保存判断出来的素数
		for(int i = start; i <= end; i++){
			if(isPrime(i)){
				list.add(i);
			}
		}
			
		System.out.println(start + " 到 " + end + " 之间的素数是 " + list + "\n总数是 " + list.size());

	}
	
	/**
	 * 
	 * @param int number 
	 * @return boolean (true is prime number, false is not prime number);
	 */
	private static boolean isPrime(int i){
		int k = (int) Math.sqrt(i);
		if (i < 3 && i > 0)
			return true;//2、3是唯一连续的两个素数
		for (int j = 2; j < i/2+1; j++){
			if(i%j == 0)	//如果余数为0,表示被1和自己之外的数整除了,即非素数,属于合数
				return false;
		}
		return true;
	}
}


根据素数定义,判断一下,除了1和本身之外的数字,只要不能把本身整除,那么证明这个数字就是素数了。

因此想要从1到数字本身一次判断余数是否为0,

然后又想,当循环超过数字本身一半之后就已经不可能在有整除的情况出现了,因此,循环可以减少一些,控制条件改正 本身除以2

但是对于4这样的小数的时候有问题,因此修改为 本身/2+1,这样可以了。

看到很多地方使用的是  Math.sqrt(本身);   表示不明所以。快哭了











版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Vega prime
Vega prime
0 0
【欧拉计划第 7 题】第 10001 个素数 10001st prime
【欧拉计划第 7 题】第 10001 个素数 10001st prime
0 0
Next Fibonacci Number(下一个斐波拉契数列)
Write a program that takes input of integer N, followed by N more integers. For each integer, output the next fibonacci number after it.
828 0
求四百万以内Fibonacci(number)数列偶数结果的总和
又对啦。。。开心~~~~ 只是代码可能不符合PEP标准什么的。。。 Each new term in the Fibonacci sequence is generated by adding the previous two terms.
503 0
+关注
算精通
北京阿里云ACE会长
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载