java筛法求N以内素数个数
答案:1 悬赏:0 手机版
解决时间 2021-01-15 14:48
- 提问者网友:川水往事
- 2021-01-14 19:56
java筛法求N以内素数个数
最佳答案
- 五星知识达人网友:神鬼未生
- 2021-01-14 20:54
prime[k]数组越界了。
没必要搞这么复杂吧。
public class Test{
public static void main(String [] args){
System.out.println("Welcome new world:++"+add(13));
}
public static int add(int n){
int cnt=0;
for(int i=2;i<=n;i++){
boolean flag = false;
for(int j=2;j
if(i%j==0){
flag = true;
}
}
if(!flag){
cnt ++;
}
}
return cnt;
}追问报错就是说越界了啊
你的代码复杂度O(n²)了吧。在我的方案上咋修改,追答public class Test{
public static void main(String [] args){
System.out.println("Welcome new world:++"+add(13));
}
public static int add(int n){
//定义计数器
int cnt=0;
//循环2到n之间的数,1排除,直接从2开始。
for(int i=2;i<=n;i++){
//先假设循环子是素数,定义标记。
boolean flag = false;
//用2到循环子之间的数去除这个循环子。如果能除尽,那该数就不是素数。
for(int j=2;j
if(i%j==0){
//不是素数
flag = true;
}
}
//如果是素数,计数器自加。
if(!flag){
cnt ++;
}
}
return cnt;
}
关键你这一块有什么 意义
for(int k=i*i;k prime[k]=false;
你没有判断该数是否是素数的判断啊。追问把for(int k=i*i;k 改成for(int k=i*2;k 就对了。这块的意思是去掉素数prime[i]的倍数(去掉合数)。
我想用k=i*i作为起始,是因为k=i*2=2*i,在i=2的时候prime[i*2]已经去掉了,没必要再重复
没必要搞这么复杂吧。
public class Test{
public static void main(String [] args){
System.out.println("Welcome new world:++"+add(13));
}
public static int add(int n){
int cnt=0;
for(int i=2;i<=n;i++){
boolean flag = false;
for(int j=2;j
if(i%j==0){
flag = true;
}
}
if(!flag){
cnt ++;
}
}
return cnt;
}追问报错就是说越界了啊
你的代码复杂度O(n²)了吧。在我的方案上咋修改,追答public class Test{
public static void main(String [] args){
System.out.println("Welcome new world:++"+add(13));
}
public static int add(int n){
//定义计数器
int cnt=0;
//循环2到n之间的数,1排除,直接从2开始。
for(int i=2;i<=n;i++){
//先假设循环子是素数,定义标记。
boolean flag = false;
//用2到循环子之间的数去除这个循环子。如果能除尽,那该数就不是素数。
for(int j=2;j
if(i%j==0){
//不是素数
flag = true;
}
}
//如果是素数,计数器自加。
if(!flag){
cnt ++;
}
}
return cnt;
}
关键你这一块有什么 意义
for(int k=i*i;k
你没有判断该数是否是素数的判断啊。追问把for(int k=i*i;k
我想用k=i*i作为起始,是因为k=i*2=2*i,在i=2的时候prime[i*2]已经去掉了,没必要再重复
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯