质数——6N±1法

6N±1法求素数

  任何一个自然数,总可以表示成为如下的形式之一:

  6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…)

  显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,除了2和3之外,所有的素数都可以表示成6N±1的形式(N为自然数)。

  根据上述分析,我们只对形如6 N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。

  以下代码需要自然数大于10 。

  public int[] getPrimes(int n){

  int []a = new int[200];

  int k=0;

  int num = 5;

  a[0]=1;a[1]=2;a[2]=3;a[3]=5;a[4]=7;

  for(int i=3;i< p>

  for(int j=0;j<2;j++){

  k = 2*(i+j)-1;

  if((k<n)&&k%5==0?false:k%7==0?false:true){< p>

  a[num] = k;

  num++;

  }

  }

  }

  return a;

  }

上一篇:phpcms v9文章内容页调用上一篇下一篇的方法(转)


下一篇:poj 3048 Max Factor(素数筛)