① java语言：请输入一个整数，并判断他是否为素数 急！！ 正在考试
1. 根据概念判断:
如果一个正整数只有两个因子, 1和p，则称p为素数.
public boolean isPrime(int n)
{
if(n < 2) return false;
for(int i = 2; i < n; ++i)
if(n%i == 0) return false;
return true;
}
时间复杂度O(n).
2. 改进, 去掉偶数的判断
public boolean isPrime(int n)
{
if(n < 2) return false;
if(n == 2) return true;
if(n%2==0) return false;
for(int i = 3; i < n; i += 2)
if(n%i == 0) return false;
return true;
}
时间复杂度O(n/2), 速度提高一倍.
3. 进一步减少判断的范围
定理: 如果n不是素数, 则n有满足1< d<=sqrt(n)的一个因子d.
证明: 如果n不是素数, 则由定义n有一个因子d满足1< d< n.
如果d大于sqrt(n), 则n/d是满足1< n/d<=sqrt(n)的一个因子.
public boolean isPrime(int n)
{
if(n < 2) return false;
if(n == 2) return true;
if(n%2==0) return false;
for(int i = 3; i*i <= n; i += 2)
if(n%i == 0) return false;
return true;
}
时间复杂度O(Math.sqrt(n)/2), 速度提高O((n-Math.sqrt(n))/2).
4. 剔除因子中的重复判断.
定理: 如果n不是素数, 则n有满足1< d<=Math.sqrt(n)的一个"素数"因子d.
证明: I1. 如果n不是素数, 则n有满足1< d<=Math.sqrt(n)的一个因子d.
I2. 如果d是素数, 则定理得证, 算法终止.
I3. 令n=d, 并转到步骤I1.
由于不可能无限分解n的因子, 因此上述证明的算法最终会停止.
// primes是递增的素数序列: 2, 3, 5, 7, ...
// 更准确地说primes序列包含1->Math.sqrt(n)范围内的所有素数
public boolean isPrime(int primes[], int n)
{
if(n < 2) return false;
for(int i = 0; primes[i]*primes[i] <= n; ++i)
if(n%primes[i] == 0) return false;
return true;
}
5. 构造素数序列primes: 2, 3, 5, 7, ...
由4的算法我们知道, 在素数序列已经被构造的情况下, 判断n是否为素数效率很高;
下面程序可以输出素数表.
public class ShowPrimeNumber{
public static int[] getPrimeNums(int maxNum){
int[] primeNums = new int[maxNum/2+1];
int sqrtRoot;
int cursor = 0;
boolean isPrime;
for(int i=2;i<=maxNum;i++){
sqrtRoot = (int)Math.sqrt(i); //取平方根
isPrime = true;
for(int j=0;j< cursor;j++){
if(primeNums[j]>sqrtRoot)
break;
if(i%primeNums[j]==0){
isPrime = false;
break;
}
}
if(isPrime){
primeNums[cursor++] = i;
}
}
int[] result = new int[cursor];
System.array(primeNums,0,result,0,cursor);
return result;
}
public static void main(String[] args) throws Exception{
int maxNum = Integer.parseInt(args[0]);
int[] primeNums = getPrimeNums(maxNum);
System.out.println("共"+primeNums.length+"个素数");
for(int i=0;i< primeNums.length;i++){
System.out.print(primeNums[i]+",\t");
}
}
}
6.(在素数表中)二分查找
Arrays.BinarySearch方法:
该方法用于在指定数组中查找给定的值，采用二分法实现，所以要求传入的数组已经是排序了的。
该方法的基本语法格式为：
Static int binarySearch(byte[] a, byte key)
该方法返回数据中key元素所在的位置，如果没有key元素，则返回key应插入的位置：-（insertion point-1），如数组中的第一个元素就大于key，返回-1。
注：数组的数据类型可以是int[] byte[] short[] float[] long[] double[] char[] Object[]类型。
② JAVA 输入一个数判断其是否是素数
public class panansushu {
public static void main(String args[]) {
int x, y, j;
Scanner i = new Scanner(System.in);
System.out.print("请输入一个数：");
y = i.nextInt();
j = (int) y / 2;
for (x = 2; x <= j; x++) {
if (y % x == 0) {
System.out.println("此数不为素数");
break;
}
}
if (x > j) {
System.out.println("此数为素数");
}
}
}
③ java中怎么求素数
首先楼主应该对素数的定义已经清楚了吧?其实就是一个数,如果存在1和它本身以外,有数能整除它,这个数就不是素数.
在这里,有2个关键的变量,我估计解释一下你就能看得明白这个算法了.
1.关于变量k.变量k的作用是优化整个算法,因为比如要判断一个数13是不是素数,我们没必要从2循环到13.只要循环到对13开根号.13开根号大概是3.6多,强转为int类型后是3.也就是说只要检查2,3是否能整除13.如果不能,13肯定是一个素数.因为比如48这个数,你前面检测到被4整除等于12,那么继续循环超过Math.sqrt(48)的话,无非就是得到一个反过来的被12除等于4的结果.这个没有必要.
2.关于变量j.注意点1:j是在最外层的循环体中定义的.这个时候刚定义完,j的值是初始的0.然后j从2开始,一直到小于等于k结束.这里是控制尝试整除的循环次数.一旦发现在这个范围内有数能整除i,那么就跳出循环.
所以,对于你不理解的那个部分,首先确定一点,程序只要执行到break,就说明这个数是素数.
例如我们这次k = 10,那么是要从j = 2到10逐一检测 i 是不是能被 j 整除.当j = 7的时候比如可以整除了,就跳出当前内层循环了.这时候, j 显然是不大于 k 的,因为只要是中途跳出,因为内层循环(j = 2; j <= k; j++)的控制,只要在循环过程中跳出来的,那么j 肯定 <= k.
只有循环到j = 10依然没有break的话,根据for循环的执行顺序,会执行j++,然后去判断j <= k 是否为true,为true则继续下一次循环,否则循环结束.而在这里,如果到10还没有能够整除的话,j是会在10的基础上自增的.这时候j就=11了.
那么if ( j > k )就不成立了,则i 不会被输出.
总结一点:就是如果中途or最后一次循环,找到能整除的数了,那么因为break的关系,最后就不会执行 j++, 所以j <= k的条件是能保证的. 换言之,如果j > k (亦即j <= k 的取反)表示没有找到能整除的数.其实j最大也就只能等于k+1.
另外,,你也可以自己修改修改,来加深理解.例如
boolean isPrime; //定义布尔变量判断是否素数.是:true;否:false
for (int i = 3; i <= 100; i++) {
isPrime = true;
int k = (int) Math.sqrt(i);
for (int j = 2; j <= k; j++) {
if (i % j == 0) {
isPrime = false; //如果能够有数整除i,那么就不是素数.
break;
}
}
if (isPrime) {
System.out.println(i);
}
}
这样就没有必要在外层循环里就定义j这个变量了.如果我上面说的你理解还是比较困难,可以先理解用布尔变量来控制的写法.这个理解了,用j > k 判断的就也很容易理解了.
④ 用java语言判断一个数是不是质数
下面是我用JavaScript写的素数函数，供参考，大同小异
PrimeA=function(n,nth){/* 小于n的素数表
参数nth 指定返回第n个素数
*/
//vart0=Time.now5();
/*
方法1：利用isPrime 废弃！
vart=[];
for(vari=2;i<n+1;i++){
if(isPrime(i)){
t.push(i)
}
}
consolelog('方法1：耗时：'+(+Time.now5()-(+t0)));
returnt
*/
//方法2：利用筛法
varp=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59];//自己往后补充，越多越好，可以加快检测小素数的效率
if(nth&&n<=669){
returnp[n-1]
}
if(!nth&&n<2){
return[]
}
if(n<=5000&&!nth){
for(vari=0;i<100;i++){
varj=p.indexOf(n-i);
if(j>-1){returnp.slice(0,j+1)};
}
returnp
}
varm=nth?Math.ceil(n*Math.log(n)+1000):n; //pn∼nln(n)
// for(vari=5001;i<=m;i+=2){
vari=5001;
while(i){
vart=Math.floor(Math.sqrt(i)),pl=p.length;
for(varj=0;j<pl;j++){//p.length
if(i%p[j]==0){
break
}elseif(p[j+1]>t){
p.push(i);
if(nth&&pl==n-1){
returni
}
break;
}
}
if(!nth&&i>=n-1){
returnp
}
i+=2;
}
returnp
//方法3：Wilson测试
}