思路:

给定n,求1~n间的素数,一般有以下几种方法

1.傻瓜解法:n,n/2

#define f(x, y) for((x); y; (x)++)
typedef long long ll;
ll prime[N] = { 0 };

void fetch_prime(ll n)
{
  ll i = 2, j, step = 0;
  f(i, i < n)
  {
    j = 2;
    f(j, j < i/ 2)
    {
      if (i % j == 0)
        break;
    }
    if (i == n)
      prime[step++] = i;
  }
}

只比用纸笔算的来的快


 

2.一般解法:√n

#define f(x, y) for((x); y; (x)++)
typedef long long ll;
ll prime[N] = { 0 };

void fetch_prime(ll n)
{
  ll i = 2, j, step = 0;
  f(i, i < n)
  {
    j = 2;
    f(j, j* j < i)
    {
      if (i % j == 0)
        break;
    }
    if (i == n)
      prime[step++] = i;
  }
}

稍微快一些

3.普通筛法:素数的倍数一定不是素数

4.线性筛法:不重复筛去

//线性素数筛
#define f(x, y) for((x); y; (x)++)
typedef long long ll;
const ll N = 100000;
ll prime[N] = { 0 }, prime_num = 0;
int is_NotPrime[N] = { 1,1 };

void fetch_prime()
{
  ll i = 2;
  f(i, i < N)
  {
    if (!is_NotPrime[i])
    {
      prime[prime_num++] = i;
    }
    ll j = 0;
    f(j, j < prime_num&& i* prime[j] < N)
    {
      is_NotPrime[i * prime[j]] = 1;
      if (!(i % prime[j]))
        break;
    }
  }
}

证明:

1、没有重复筛

一个合数可以被分解成p[1]*p[2]*…p[n],并且保证p[1]<p[2]<…<p[n]。例如,在n=3时,筛掉这个合数的机会有:p[1]和p[2]*p[3],p[2]和p[1]*p[3],p[3]和p[1]*p[2],而我们选择的那个质数必须小于那个合数的最小质因子,如p[2]和p[1]*p[3],因为p[2]>p[1],所以这样是筛不到的。唯一会筛的是第一种:p[1]和p[2]*p[3]。

2、没有漏筛

还是假设把这个合数分解质因数p[1]*p[2]*…p[n],保证p[1]<p[2]<…<p[n],在n=3时,我们设s=p[2]*p[3],s肯定小于刚才那个合数,说明肯定对于它已经筛过,然后p[1]肯定小于s,因为s=p[2]*p[3],即p[1]是最小的因子。说明p[1]*s也就是这个合数一定筛过。

证明看不明白就背代码吧。。。

打赏 赞(1)
支付宝二维码图片

支付宝扫描二维码打赏

发表评论

电子邮件地址不会被公开。

Scroll Up