词条 | 筛法求素数 |
释义 | 基本思想用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。如有: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1不是素数,去掉。剩下的数中2最小,是素数,去掉2的倍数,余下的数是: 3 5 7 9 11 13 15 17 19 21 23 25 27 29 剩下的数中3最小,是素数,去掉3的倍数,如此下去直到所有的数都被筛完,求出的素数为: 2 3 5 7 11 13 17 19 23 29 C语言实现#define RANGE 200 #include <stdio.h> void main(void) { int sieve[RANGE + 1]; int i,j,count; for(i = 0;i <= RANGE;i ++) sieve[i] = 1;//初始化 sieve[0] = sieve[1] = 0;//0和1不是素数 count = 0; for(i = 2;i <= RANGE;i ++) if(sieve[i] == 1)//i是素数 { printf("%5d",i);//输出素数 count ++; if(count % 8 == 0)//每行输出8个值 printf("\"); for(j = i;j <= RANGE; j += i) sieve[j] = 0;//筛去i的倍数 } printf("\"); } pascal实现:maxfactor:=trunc(sqrt(maxp));//筛法求素数 fillchar(sieve,sizeof(sieve),true); for i:=2 to maxfactor do if sieve[i] then begin newp:=i+i; while newp<=maxp do begin sieve[newp]:=false; newp:=newp+i;//每次取出这个数的倍数 end; end; C++实现:#include <iostream> using namespace std; void FilterPrime(int n) { bool* isPrimes = new bool[n+1]; for(int i=2;i<=n;++i) { isPrimes[i] = true; } isPrimes[2] = true; for(int j=2;j<=n;++j) { if(isPrimes[j]==true) { for(int m=2;j*m<=n;++m) { isPrimes[j*m] = false; } } } for(int k=2;k<=n;++k) { if(isPrimes[k]==true) { cout<<k<<"是素数"<<endl; } } delete [] isPrimes; } int main() { int num; cin>>num; FilterPrime(num); system("pause"); return 0; } python 实现:#!/usr/bin/env python #-*- coding:utf-8 -*- alist = [2, 3] def isornot(anum, a): for i in a: if anum % i == 0: return False a.append(anum) return True for e in range(2,100000): isornot(e, alist) print alist |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。