2 weixin 39520967 weixin_39520967 于 2017.07.16 17:34 提问

求解,(不要用数组)。。。。

将大于整数m且紧靠m的k个素数输出。列如,若m的值为17,k的值为5,则应输出19,23,29,31,37。m和k的值从键盘输入。

5个回答

qq_28249373
qq_28249373   2017.07.16 20:11

#include
#include

int main()
{
int m, k;

scanf_s("%d%d", &m, &k);

//从m+1开始枚举,寻找与m最近的素数
for (int i = m + 1;k>0 ;i++)
{
    int n = (int)sqrt(i);//一个合数的最小约数不会超过它本身的开方(1 除外)
    int j;

    //判断一个数是不是素数
    for (j = 2;j <= n;j++)
    {
        if (i%j == 0)break;//一旦能整除,就是合数,结束循环
    }

    //如果j>n,说明上一个for循环没有中断,也就是说从2到它本身的开方n之间没有约数,因此这个数i是素数。
    if (j >n) {
        printf("%d\n", i);
        k--;
    }

}

}


qq_28249373
qq_28249373   2017.07.16 20:13

这个方法不是最高效的。求素数还有更好的方法。这个就是代码量比较小。

qq_28249373
qq_28249373   2017.07.16 20:16
 #include<math.h>//使用sqrt函数要包含数学库
weixin_38358654
weixin_38358654   2017.07.17 11:10

package Ans;
public class Demo1 {
public static boolean CheckPrime(int Pr){
if(Pr%(Pr/2)==0)
return false;
int MaxSub=(Pr/2)-1;
int Mod1=0;
int Mod2=0;
for(int temp=1;temp<Pr/6;temp++){
Mod1=Pr%MaxSub;
Mod2=Pr%(MaxSub-2);
if((Mod1==0)||(Mod2==0))
return false;
if((Mod1!=1)&&(Mod2!=1)){
if((Mod1%Mod2==0)){
return false;
}
}
MaxSub=MaxSub-3;//步长为3
}
return true;
}
public static void GetThePrimeNum(int M,int K)
{
//首先判断M说不是素数
if(CheckPrime(M)){
//寻找和M靠的最近的K个素数
int count=1;
int index=0;
while(index<K){
if(CheckPrime(M+2*(count++))){
System.out.print(M+2*(count-1)+" ");
index+=1;
}
}
}
}
public static void main(String[] args){
/**
* 我用java实现,好不好。这本来是个比较简单的问题,令M=17 k=10
* 说明问题就可以了。
* **/
GetThePrimeNum(17,10);
}
}
输出结果:
19 23 29 31 37 41 43 49 53 61


weixin_38358654
weixin_38358654   2017.07.17 11:12

最多只需要比较需要比较的1/3的

Csdn user default icon
上传中...
上传图片
插入图片