Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4236537
  • 博文数量: 553
  • 博客积分: 13864
  • 博客等级: 上将
  • 技术积分: 11041
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-28 21:25
个人简介

个人Blog: hhktony.com

文章分类

全部博文(553)

文章存档

2015年(1)

2014年(2)

2013年(12)

2012年(384)

2011年(154)

分类: LINUX

2012-01-05 02:37:55

根据初等数论,一个整数不能整除他的平方数之内的整数就是素数..

比较简单的方法:

点击(此处)折叠或打开

  1. #include <stdio.h>

  2. int main(int argc, char *argv[])
  3. {
  4.     int n,r,i;
  5.     scanf("%d",&n);

  6.     for(i = 2; i < n; i++)
  7.     {
  8.         r = n % i;
  9.         if(r == 0)
  10.             break;
  11.      }

  12.     if(i >= n)
  13.         printf("yes\n");
  14.     else
  15.         printf("no\n");

  16.     return 0;
  17. }

以上这种方法比较容易理解,但是需要的时间比较长,因为系统要将所有的数字进行比较运算,而实际上我们可以将偶数去掉,甚至我们只需要循环到到根号下N+1就够了。

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <math.h>

  3. #define YES 1
  4. #define NO 0

  5. int isprime(int num)
  6. {
  7.     int i, j;

  8.     if (num == 2)
  9.         return YES;
  10.     else if (num < 2 || num % 2 == 0)
  11.         return NO;
  12.     else
  13.     {
  14.         j = (int)sqrt(num + 1);
  15.         for (i = 3; i <= j; i = i + 2)
  16.             if (num % i == 0)
  17.                 return NO;
  18.     }

  19.     return YES;
  20. }

  21. int main(int argc, char *argv[])
  22. {
  23.     int N;
  24.     scanf("%d", &N);

  25.     if (isprime(N) == YES)
  26.         printf("yes\n");
  27.     else
  28.         printf("no\n");

  29.     return 0;
  30. }
阅读(1423) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~