首页 > 代码库 > 素数筛
素数筛
这是我目前知道的打素数表最快的方法了………… 差不多是O(n)的,100000以内花了0.005秒。
1 int prime[100005], np, vis[100005]; 2 3 void get_prime(int n){ 4 mset(prime); mset(vis); 5 np = 0; 6 for(int i = 2; i < n; i++){ 7 if(vis[i] != 1) 8 prime[np++] = i; 9 for(int j = 0, t; j < np && (t = prime[j]*i) < n; j++){ 10 vis[t] = 1; 11 if(i % prime[j] == 0) break; 12 } 13 } 14 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。