大家好，欢迎来到IT知识分享网。
先实现高效的素数筛选法
然后再暴力的无平方数筛选法
然后再高效的平方数筛选法
bool vis[1000000 + 5]; //首先实现最高效的素数筛选 void creat_primer_table(int m) { for(int i = 2;i * i <= m;i++) { if(!vis[i]) { for(int j = i * i;j <= m;j++) { vis[j] = 1; } } } }
以上代码是最高效的素数筛选法，有几个要点需要说一下啊，首先是基底必须是素数，这部分是靠!vis[i]实现的，然后是从i*i开始筛选
下面是暴力的无平方数的筛选
bool vis[10000000 + 5];//先实现暴力求解的方式 bool is_no(int x) { for(int i = 2;i * i <= x;i++) { if(x % (i * i) == 0) return false; } return true; }
非常的暴力而且没有技术含量，这个函数只是用来判断是不是无平方数，在主函数中还需要有一个循环来配合
下面是高效的无平方数的筛选
bool vis[1000000 + 5];//vis[0]代表n是不是无平方数
void creat_table(int n,int m) { for(int i = 2;i * i <= m;i++) { int p = i * i; int pos = n; //其实在这个地方只能挑选素数 for(;;) { if(pos % p != 0) { pos++; } else break; } for(;pos <= m;pos = pos + p) { vis[pos - n] =1; } } }
主要在第二层循环的第一个循环处，因为必须首先找到一个平方数的倍数，才能够开始进行筛选
其中vis[]数组的含义已经写在了代码的注释中了，在主函数中相应的输出部分，应该多加注意
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/32522.html
