欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言程序设计100例之(12):Eratosthenes筛法求质数

程序员文章站 2023-08-23 09:27:34
例12 Eratosthenes筛法求质数 问题描述 Eratosthenes筛法的基本思想是:把某范围内的自然数从小到大依次排列好。宣布1不是质数,把它去掉;然后从余下的数中取出最小的数,宣布它为质数,并去掉它的倍数。在第1步之后,得到质数2,筛中只包含奇数;第2步之后,得到质数3,一直做下去,当 ......

例12   eratosthenes筛法求质数

问题描述

eratosthenes筛法的基本思想是:把某范围内的自然数从小到大依次排列好。宣布1不是质数,把它去掉;然后从余下的数中取出最小的数,宣布它为质数,并去掉它的倍数。在第1步之后,得到质数2,筛中只包含奇数;第2步之后,得到质数3,一直做下去,当筛中为空时结束。

用eratosthenes筛法求给定区间内的所有质数。

输入格式

两个整数a和b,其中1≤a≤b≤10000

输出格式

输出给定范围[a,b]间的所有质数,输出时每个质数占6列,每行输出10个质数。

输入样例

100  200

输出样例

101  103  107  109  113  127  131  137  139  149 

151  157  163  167  173  179  181  191  193  197

199

        (1)编程思路。

        下面采用自顶向下逐步求精的方法解决这个问题。

1)先写出程序的总体框架

初始化,将所有的数都放在筛子中;

k=2;

while(k<=n)

{

     用k将筛子中的数2*k、3*k、4*k …,一一筛去;

      从当前下标k的下一个开始找到下一个仍在筛子中的数,并赋值给k;

}

从2开始,将所有留在筛子中的数(即为质数)打印出来;

2)筛子的构造

为了表示一个筛子,并将给定范围n以内的数放入筛子中,可以定义一个一维数组

int  prime[n+1];

其中,元素prime[i]==1表示整数i在筛子中;prime[i]==0表示整数i不在筛子中。

因此,初始化数组prime使所有的数都在筛子中,即使prime[2]~ prime[n]的值全部等于1。程序描述为:

     for (k=2; k<=n;k++)

              prime[k]=1;

3)用k将筛子中的数2*k、3*k、4*k …,一一筛去

n=2;

while(n*k<n)

{

    prime[n*k]=0;

    n++;

 }

4)从当前下标k的下一个开始找到下一个仍在筛子中的数,并赋值给k

k++;

while(prime[k]==0)

     k++;

5)从a开始到b为止,将仍然在筛子中的数打印出来

for (k=a; k<=b; k++)

{

     if(prime[k])  printf(“%d  “,k);

}

(2)源程序。

#include <stdio.h>

#define n 100000

int main()

{

         int prime[n+1]={0,0},t,k,cnt,a,b;

         for (k=2; k<=n;k++)

                   prime[k]=1;

         k=2;

         while(k<=n)

         {

                   t=2;

                   while(t*k<=n)

                   {

                            prime[t*k]=0;

                            t++;

                   }

                   k++;

                   while(k<=n  && prime[k]==0)

                            k++;

         }

         scanf("%d%d",&a,&b);

         cnt=0;

         for (k=a;k<=b;k++)

        {

            if (prime[k]==1)

           {

                 cnt++;

                printf("%6d",k);

                 if (cnt%10==0)  printf("\n");

          }

     }

    printf("\n");

    return 0;

}

习题12

12-1  质因子分解

        本题选自洛谷题库 (https://www.luogu.org/problem/p2043)

题目描述

对n!进行质因子分解。

输入格式

输入数据仅有一行包含一个正整数n,n<=10000。

输出格式

输出数据包含若干行,每行两个正整数p,a,中间用一个空格隔开。表示n!包含a个质因子p,要求按p的值从小到大输出。

输入样例

10

输出样例

2 8

3 4

5 2

7 1

说明/提示

10!=3628800=(2^8)*(3^4)*(5^2)*7

 (1)编程思路。

先看如何求n!中质因子k的个数。以求10!质因子2的个数为例说明。

设先将1~10共10个数排成一行得到序列1。且设保存2的因子个数的变量cnt的初值为0。

    序列1:     1  2  3  4  5  6  7  8  9  10

在序列1中,只有2、4、…、10 共 10/2=5个数中至少含有一个2的因子。故cnt=cnt+n/2=0+5=5。

    将序列1中的每个数除以2,只保留得到的整数,可排成序列2。(对应操作为n=n/2)

    序列2:                 1  2  3  4   5

  对应序列1的数为:2  4  6   8  10

    在序列2中,有5个数,只有5/2=2个数含有因子2,即原序列中有2个数(4,8)至少含有两个因子2。  cnt=cnt+n/2=5+5/2=7。

    再将序列2中的每个数除以2,只保留得到的整数,可排成序列3。(对应操作为n=n/2)

    序列3                  1   2    

对应序列1的数为:4   8

在序列3中,有2个数,只有2/2=1个数含有因子2,即原序列中有1个数(8)至少含有三个因子2。  cnt=cnt+n/2=7+2/2=8。

    再将序列3中的每个数除以2,只保留得到的整数,可排成序列4。(对应操作为n=n/2)

    此时,序列4中不再有数能被2整除,即原序列中没有数含有4个2的因子。

       cnt=cnt+n/2=8+1/5=8。  

    至此,求得10!含有质因子2的个数为8。

按上述过程,将求n!中质因子k的个数写成一个简单的循环即可。

        cnt=0;

        while (n!=0)

        {

            cnt+=n/k;

            n/=k;

        }

定义数组int prime[1250]保存所有小于10000的质数,如prime[0]=2,prime[1]=3, prime[2]=5,…。用筛法求出各质数并保存在prime数组中。

定义数组int num[1250],其中num[i]保存n!中质因子prime[i]的个数,num数组的全部元素的初始值置为0。

程序中按前面介绍的求n!中质因子k的个数的方法,用循环依次求取小于或等于n的质数prime[i]的个数num[i]。

 (2)源程序。

#include <stdio.h>

#define n 10000

int main()

{

    int t,k,i,n,cnt;

         int flag[n+1]={0,0};

         int prime[1250],num[1250]={0};

         for (k=2; k<=n;k++)

                   flag[k]=1;

         k=2; cnt=0;

         while(k<=n)

         {

                   t=2;  prime[cnt++]=k;

                   while(t*k<=n)

                   {

                            flag[t*k]=0;

                            t++;

                   }

                  k++;

                 while(k<=n && flag[k]==0)

                       k++;

         }

         scanf("%d",&n);

         for (i=0;i<cnt;i++)

        {

              if (prime[i]>n) break;

              t=n;

             while (t!=0)

            {

                  num[i]+=t/prime[i];

                  t/=prime[i];

           }

    }

    for (k=0;k<i;k++)

       printf("%d %d\n",prime[k],num[k]);

   return 0;

}

12-2  prime gap

        本题选自北大poj题库 (http://poj.org/problem?id=3518)

description

the sequence of n − 1 consecutive composite numbers (positive integers that are not prime and not equal to 1) lying between two successive prime numbers p and p + n is called a prime gap of length n. for example, ‹24, 25, 26, 27, 28› between 23 and 29 is a prime gap of length 6.

your mission is to write a program to calculate, for a given positive integer k, the length of the prime gap that contains k. for convenience, the length is considered 0 in case no prime gap contains k.

input

the input is a sequence of lines each of which contains a single positive integer. each positive integer is greater than 1 and less than or equal to the 100000th prime number, which is 1299709. the end of the input is indicated by a line containing a single zero.

output

the output should be composed of lines each of which contains a single non-negative integer. it is the length of the prime gap that contains the corresponding positive integer in the input if it is a composite number, or 0 otherwise. no other characters should occur in the output.

sample input

10

11

27

2

492170

0

sample output

4

0

6

0

114

        (1)编程思路。

        题目的意思是:两个连续质数a和b之间的区间称为非质数区间。求n所在非质数区间的长度。例如,23和29是两个连续的质数,23和29之间的区间就是一个非质数区间,这个区间的长度为6,整数27在这个区间中,因此27所在非质数区间的长度为6。

        定义数组int prime[maxn],元素prime[i]的值为0表示整数i是质数(在筛子中,没有被筛掉),prime[i]的值为1表示整数i是不是质数(不在筛子中,已经被筛掉了)。

        初始时prime的数组元素初值全为0,表示给定范围的每个整数都在筛子中。用筛法将所有的非质数全筛掉。

        为求取n所在非质数区间的长度。若n本身是一个质数,则其所在非质数区间的长度记为0。

         若n不是一个质数,可用循环 for (left=n-1; prime[left]==1;  left--);求得比n小的最大质数left;用循环for (right=n+1;prime[right]==1; right++);求得比n大的最小质数right。则n一定在连续质数left和right之间的非质数区间,区间长度为right-left。

        (2)源程序。

#include <stdio.h>

#define maxn 1399710

int prime[maxn]={0};

int main()

{

    int i,j,n,left,right;   

    for(i=2;i<maxn;i++)

    {

        if(prime[i]==0)

        {

            for (j=i*2;j<maxn;j+=i)

              prime[j]=1;

        }

    }

    while (scanf("%d",&n) && n!=0)

    {

        if(prime[n]==0)

        {

            printf("0\n");

            continue;

        }

        else

        {

              for (left=n-1; prime[left]==1;  left--);

              for (right=n+1;prime[right]==1; right++);

              printf("%d\n",right-left);

          }

    }

    return 0;

}

12-3  largest prime factor

        本题选自杭州电子科技大学oj题库 (http://acm.hdu.edu.cn/showproblem.php?pid=2136)

problem description

everybody knows any number can be combined by the prime number.

now, your task is telling me what position of the largest prime factor.

the position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc.

specially, lpf(1) = 0.

input

each line will contain one integer n(0 < n < 1000000).

output

output the lpf(n).

sample input

1

2

3

4

5

sample output

0

1

2

1

3

        (1)编程思路。

本题题意是:求一个整数n的最大质因子在质数表中排第几。比如,9的最大质因子是3,3在质数表中排第2;5的最大质因子为5,在质数表中排第3。

定义数组int rank[n],元素prime[i]的值表示整数i的最大质因子在质数表中排第几。

初始时rank的数组元素初值全为0,表示尚未确定每个数的最大质因子的排位值。同时,借助筛法的思想。rank的数组元素初值全为0,表示给定范围(1~n)的每个整数都在筛子中。

在前面介绍的筛法中,我们只是简单置数组元素值为0或为1,表示在或不在筛子中,本题中rank数组元素值除了表示在或不在筛子中的含义外,非0的元素值还表示最大质因子在质数表中的排位值。为此,修改的筛法执行过程描述如下:

1)初始时,令i=2,cnt=1,表示最小的质数为2,其排位值为1。

2)2<=n,rank[2]=0,cnt=1表示2是排位为1的质数。同时修改rank[2]、rank[4]、rank[6]、rank[8]、rank[10]……等元素的值为1(当前cnt=1),这个修改既表示将2的倍数的数从筛子中筛掉,同时表示这些2的倍数的数当前确定的最大质因子的排位号为1。 cnt++表示下一个质数的排位值为2。

3)i++,i=3,此时rank[3]=0表示3在筛子中,3是质数,cnt=2,表示3是排位值为2的质数。同时修改rank[3]、rank[6]、rank[9]、rank[12]、rank[15]……等元素的值为2(当前cnt=2),这个修改既表示将3的倍数的数从筛子中筛掉,同时表示这些3的倍数的数当前能确定的最大质因子的排位号为2。 cnt++表示下一个质数的排位值为3。

4)i++,i=4,rank[4]=1不为0,表示4不在筛子中,4不是质数,能确定它的最大质因子的排位值为1。不处理,直接跳过。

5)i++,i=5,此时rank[5]=0表示5在筛子中,5是质数,cnt=3,表示5是排位值为3的质数。同时修改rank[5]、rank[10]、rank[15]、rank[20]、rank[25]……等元素的值为3(当前cnt=3),这个修改既表示将5的倍数的数从筛子中筛掉,同时表示这些5的倍数的数当前能确定的最大质因子的排位号为3。 cnt++表示下一个质数的排位值为4。

……

重复上面的过程,直到i>n。此时1~n范围内所有整数的最大质因子在质数表中的排位值都确定了,且保存在数组rank的相应元素中。

(2)源程序。

#include <stdio.h>

#define n 1000000

int rank[n+1]={0};

int main()

{

    int i,j,n,cnt=1;

    for (i=2;i<=n;i++)

    {

        if(rank[i]!=0) continue;

        for (j=i;j<=n;j+=i)

           rank[j]=cnt;

        cnt++;

    }

    while (scanf("%d",&n)!=eof)

         printf("%d\n",rank[n]);

    return 0;

}