服装定制网站源码,腾讯公司,怎么做代刷网站长,网站建设学院我们首先先来了解一下什么是素数
素数:一个整数只能被1和自身整除 , 注意:0与1不是素数 目录
方法一:暴力法 方法二:除二法(优化)
方法三.根号法(最优法) 方法一:暴力法
最简单最暴力的方法就是根据定义#xff0c;判断n是不是素数,让n除以2到n-1的所有数,只要遇到能除开… 我们首先先来了解一下什么是素数
素数:一个整数只能被1和自身整除 , 注意:0与1不是素数 目录
方法一:暴力法 方法二:除二法(优化)
方法三.根号法(最优法) 方法一:暴力法
最简单最暴力的方法就是根据定义判断n是不是素数,让n除以2到n-1的所有数,只要遇到能除开的,就证明n一定不是素数 , 因为如果n为素数则只有1和n为因数。
public class Text {public static void main(String[] args) {System.out.println(请输入一个整数 );Scanner scanner new Scanner(System.in);int n scanner.nextInt();if(n0||n1){System.out.println(n不是素数);}int i 2;for (; i n - 1; i) {if (n % i 0) {System.out.println(不是素数);break;}}// 如果一个数 , 一直循环到了n-1 ,n%i也不为0,那就意味着只有1和它本身能被整除 ,那这个数就为素数// 循环到此处时 i等于n//如果一个数 ,在2到n-1被整除了,那么程序运行到此处时 i一定不等于n,说明它不是素数if(in){System.out.println(n是素数);}}
} 方法二:除二法(优化)
将循环范围定在2到n/2原理任何一个数的最大因数都小于等于它的二分之一所以只要从2查找到n/2如果都没有被整除即为素数因为到这里已经查找到他的最大因数了,再往后的数字都是除不开的
eg:30的最大因数为15(能够被三十除近的数只能在1到15 ) 100的最大因数为50
public class Text {public static void main(String[] args) {System.out.println(请输入一个整数 );Scanner scanner new Scanner(System.in);int n scanner.nextInt();if(n0||n1){System.out.println(n不是素数);}int i 2;for (; i n/2; i) {if (n % i 0) {System.out.println(n不是素数);break;}}if(in/2){System.out.println(n是素数);}}
}方法三.根号法(最优法)
到这里我们发现虽然循环次数减半但不是最优解,而考虑1-根号n时,又缩小了范围,eg:根号17为4.123,而17/2为8.5.
下面具体讲解一下根号法的思路
当我们考虑到根号的情况时,会发现:一个数的两个因数必然会有一个大于根号n , 一个小于根号n
(因为平方根后的两个数一定是相等的,eg:16的两个根为4*4,要想使用其他情况的两种根,必然一个大于4,一个小于4,不可能一个数为4,一个数为除了4以外的数,那结果一定不为16了)
eg:100的因数有1和1002和504和255和2010和10.只要从2尝试到根号n(也就是10)如果都没有被整除就是素数否则就不是。
public class Text {public static void main(String[] args) {System.out.println(请输入一个整数 );Scanner scanner new Scanner(System.in);int n scanner.nextInt();if(n0||n1){System.out.println(n不是素数);}int i 2;double tmpMath.sqrt(n);//注意根号后的结果是double类型for (; i tmp; i) {//eg:如果temp为3.14,循环到了整数3,也无法整除,那就意味着,这个数是素数i后就会变成4if (n % i 0) {System.out.println(不是素数);break;}}if(itmp){//上方说道i后会变成4,也就是itemp,即为素数System.out.println(n是素数);}}
}
