• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C语言程序设计100例之(11):求质数 - aTeacher

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

C语言程序设计100例之(11):求质数

例11  求质数

问题描述

质数是指除了有1和自身作为约数外,不再有其他约数的数。比如:3、5、7是质数。而9不是质数,因为它还有约数3。

编写程序求给定区间中的所有质数。

输入格式

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

输出格式

输出给定范围的所有质数,输出时每个质数占5列,每行输出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)编程思路

判断一个数m是否为质数的方法是:用2~sqrt(m)中的每一个整数i去除m,若某一个i能整除m,则m不是质数;否则,m是质数。该操作可定义为一个函数,如下:

int isPrime(int m)

{

    int i;

    if (m==1) return 0;

    for (i=2;i<=sqrt(1.0*m);i++)

        if (m%i==0)  return 0;

    return 1;

}

求a~b之间的所有质数,写成一个循环,在循环中调用函数isPrime判断每个整数i是否为质数,若是,则计数并输出。

(2)源程序。

#include <stdio.h>

#include <math.h>

int isPrime(int m)

{

    int i;

    if (m==1) return 0;

    for (i=2;i<=sqrt(1.0*m);i++)

        if (m%i==0)  return 0;

    return 1;

}

int main()

{

    int i,a,b,cnt=0;

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

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

    {

        if (isPrime(i))

        {

            cnt++;

            printf("%5d",i);

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

        }

    }

    return 0;

}

习题11

11-1  回文质数

问题描述

我国古代有一种回文诗,倒念顺念都有意思,例如“人过大佛寺”,倒读起来便是“寺佛大过人”。还有经典的对联“客上天然居,居然天上客”等。在自然数中,如果一个数从左向右读或是从右向左读完全一致,这样的自然数称为回文数。

编写一个程序,找出N之内的所有回文质数。所谓回文质数就是一个数即是一个质数又是一个回文数,例如,151 是回文质数。

输入格式

一个整数N,其中1≤N≤100000。

输出格式

输出N以内的所有回文质数,输出时每个回文质数占5列,每行输出10个回文质数。

输入样例

10000

输出样例

     2    3     5    7    11  101   131   151   181   191

   313  353   373  383   727  757   787   797   919   929

  (1)编程思路。

将判断一个数是否为质数和是否为回文数分别写成一个函数。

函数int isPrime(int m);判断数m是否为质数,m是质数,函数返回值为1,否则为0。

函数int isPalm(int m); 判断数m是否为回文数,m是回文数,函数返回值为1,否则为0。

  (2)源程序。

#include <stdio.h>

#include <math.h>

int isPrime(int m)

{

    int i;

    if (m==1) return 0;

    for (i=2;i<=sqrt(1.0*m);i++)

        if (m%i==0)  return 0;

    return 1;

}

int isPalm(int m)    // 判断m是否为回文数

{

    int a,b;

    a=m; b=0;

    while (a>0)

    {

          b=b*10+a%10 ;

          a = a/10;

    }

    return b==m;

}

int main()

{

    int i,n,cnt=0;

    scanf("%d",&n);

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

    {

        if (isPalm(i) && isPrime(i))

        {

            cnt++;

            printf("%5d",i);

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

        }

    }

    return 0;

}

        从程序运行结果可以看出,回文质数除了11以外,所有回文质数的位数都是奇数。这是因为,如果一个回文数的位数是偶数,则它的奇数位上的数字之和与偶数位上的数字之和必然相等。根据数的整除性原理,这样的数肯定能被11整除。因此,回文质数的位数绝不可能是偶数(除11外)。

11-2  第N个质数

问题描述

质数就是不能再进行等分的整数。比如:7,11是质数。而9不是质数,因为它可以平分为3等份。一般认为最小的质数是2,接着是3,5,...

设“2” 是第一个质数,“3” 是第二个质数,依此类推。问第N个质数是多少?

输入格式

一个整数N,其中1≤N≤1000000。

输出格式

一个整数,它是第N个质数。

输入样例

10

输出样例

29

        (1)编程思路。

        先处理n=1,输出2的特殊情况。因为,2之后的所有质数均为奇数。

        记当前质数个数cnt=1(2是第1个质数),从i=3开始,顺序判断当前奇数是否为质数,若是质数则cnt++,若cnt==n,则当前奇数为第n个质数,结束循环查找并输出结果。

        (2)源程序。

#include <stdio.h>

#include <math.h>

int isPrime(int m)

{

    int i;

    if (m==1) return 0;

    for (i=2;i<=sqrt(1.0*m);i++)

        if (m%i==0)  return 0;

    return 1;

}

int main()

{

   int n,i,cnt;

   scanf("%d",&n);

   if (n==1) printf("2\n");

   else

   {

       cnt=1; i=3;

       while(1)

       {

          if (isPrime(i)) cnt++;

          if(cnt==n) break;

          i+=2;

       }

       printf("%d\n",i);

   }

   return 0;

}

11-3  哥德巴赫猜想(升级版)

题目描述

1742年6月7日哥德巴赫写信给当时的大数学家欧拉,正式提出了以下的猜想:任何一个大于9的奇数都可以表示成3个质数之和。质数是指除了1和本身之外没有其他约数的数,如2和11都是质数,而6不是质数,因为6除了约数1和6之外还有约数2和3。需要特别说明的是1不是质数。

这就是哥德巴赫猜想。欧拉在回信中说,他相信这个猜想是正确的,但他不能证明。

从此,这道数学难题引起了几乎所有数学家的注意。哥德巴赫猜想由此成为数学皇冠上一颗可望不可及的“明珠”。

现在请你编一个程序验证哥德巴赫猜想。

输入格式

仅有一行,包含一个正奇数n,其中9<n<20000。

输出格式

仅有一行,输出3个质数,这3个质数之和等于输入的奇数。相邻两个质数之间用一个空格隔开,最后一个质数后面没有空格。如果表示方法不唯一,请输出第一个质数最小的方案,如果第一个质数最小的方案不唯一,请输出第一个质数最小的同时,第二个质数最小的方案。

输入样例

2009

输出样例

3 3 2003

        (1)编程思路。

        对输入的正奇数n,先判断其和是否含有质数2,只有一种可能2+2+(n-4),若n-4是质数,则直接输出结果,结束。

        如果n的和值中不包含质数2,则只能分解为3个奇数之和。不妨设n=i+j+(n-i-j)。用一个二重循环寻找答案。外循环i为3~n/3之间的所有奇数,内循环j为i~n/3之间的所有奇数,在内循环中调用函数isPrime判断,若i、j、n-i-j三个数均为质数,则找到答案,输出并结束。

        (2)源程序。

#include <stdio.h>

#include <math.h>

int isPrime(int m)

{

        int k,i;

        k=sqrt(1.0*m);

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

            if (m%i == 0)   return 0;

         return 1;

}

int main()

{

    int n,i,j,flag=0;

    scanf("%d",&n);

    if (isPrime(n-4)==1)

    {

        printf("%d %d %d\n",2,2,n-4);

        return 0;

    }

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

    {

        if (isPrime(i)==0) continue;

        for (j=3;j<=n/3;j+=2)

            if (isPrime(j) && isPrime(n-i-j))

            {

                  flag=1;  break;

            }

           if (flag==1) break;

    }

    printf("%d %d %d\n",i,j,n-i-j);

    return 0;


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
LinuxC编程之六makefile项目管理发布时间:2022-07-13
下一篇:
C++中static的作用发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap