首页 > 代码库 > 线性筛法（欧拉筛法）求素数
线性筛法（欧拉筛法）求素数
时间复杂度O(n)当n比较大时欧拉筛法所用的时间比O(nloglogn)的算法的时间少的会越来越明显
为什么呢?
因为在欧拉筛法中，每一个合数只被访问并将其所对的f[]的值修改了一次。
for(i = 2; i <= n; i++){ if(f[i] == 0) { p[++cnt] = i; } for(j = 1; j <= cnt; j++) { if(i * p[j] > n)break; f[i * p[j]] = 1; if(i % p[j] == 0)break; }}
线性筛法（欧拉筛法）求素数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。