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











相关文章
素数(prime number)又称质数,有无限个。除了1和
素数(prime number)又称质数,有无限个。除了1和
10 001st prime number
这真是一个耗CPU的运算,怪不得现在因式分解和素数查找现在都用于加密运算。 By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
1045 0
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
9月前
|
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
73 0
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
117 1
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
49 0
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
117 0
LeetCode 414. Third Maximum Number