素数是个什么东西 prime number-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

素数是个什么东西 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(本身);   表示不明所以。快哭了











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

分享: