<谭> 6.8 判断m是否是素数    采用如下算法：让m被2到m^2除，如果m能被2～m^2之中任何一个整数整除，则提前结束循环，此时i必然小于或等于k(即m^2)；如果m不能被2～k(即m^2)之间的任一整数整除，则在完成最后一次循环后，i还要加1，因此i=k+1，然后才终止循环。在循环之后判别i的值是否大于或等于k+1，若是，则表明未曾被2～k之间任一整数整除过，因此输出“是素数”。#include <stdio.h>#include <math.h>int main(){    int m, i, k;    scanf("%d", &m);    k = sqrt(m);     for (i = 2; i <= k; i++)        if (m % i == 0) break;     if (i >= k + 1)        printf("%d is a prime number\n", m);    else        printf("%d is not a prime number\n", m);     return 0;}★ 素数: 大于1，并且除1和它本身外没有其他因数的自然数叫素数(或质数) ,2是最小的素数，除2以外，所有的偶数都不是素数。 6.9 求100～200间的全部素数。#include <stdio.h>#include <math.h>int main(){    int m, i, k, n = 0;    for (m = 101; m <= 200; m = m + 2)  /* 除2以外，所有偶数都不是素数 */    {        k = sqrt(m);         for (i = 2; i <= k; i++)            if (m % i == 0) break;         if (i >= k + 1)        {            printf("%d ", m);            n = n + 1;        }        if (n % 10 == 0)            printf("\n");    }    printf("\n");    return 0;}★ 用筛选法也可以做, 下章数组再续。 ★ 一个自然数是素数,且它的各位数字位置经过任意对换后仍为素数,则称是绝对素数。 [更新] 2006.11.18  [066] 筛选法求素数 [更新] 2006.11.19 今天按如上方案写了个判断素数的函数, 用其求1到100间的素数如下:#include <stdio.h>#include <math.h> int prime(int n){    int i;    int k = sqrt(n);     if(n > 1)    {        for(i = 2; i <= k; i++)            if(n % i == 0)                break;                if(i >= k + 1)            return 1;        else            return 0;    }    else        return 0;} int main(void){    int i;    int n = 0;    int a[101];     for(i = 1; i <= 100; i++)    {        if(prime(i))        {            printf("%-5d", i);            n++;        }        if(n == 10)        {            printf("\n");            n = 0;        }    }    printf("\n");    return 0;}运行结果(VC)=================================================2    3    5    7    11   13   17   19   23   2931   37   41   43   47   53   59   61   67   7173   79   83   89   97================================================= [更新] 2006.12.27今天又在一本书上看到一个判断素数的函数,虽然没对理论的上限值作约束,但看上去比上面的方法要简洁些。因为2是最小的素数，所以此函数是从2开始运行的，没有对1进行判断处理，这样就要求实参要大于等于2，求1到100以内的素数时就要从2开始做循环了，用此函数求1到100间素数如下：#include <stdio.h>#include <math.h> int prime(int n){    int i;    for(i = 2; n%i != 0; i++)        ;    return n == i ? 1 : 0;} int main(void){    int i;    int n = 0;    int a[101];     for(i = 2; i <= 100; i++)    {        if(prime(i))        {            printf("%-5d", i);            n++;        }        if(n == 10)        {            printf("\n");            n = 0;        }    }    printf("\n");    return 0;} 运行结果(VC)：=================================================2    3    5    7    11   13   17   19   23   2931   37   41   43   47   53   59   61   67   7173   79   83   89   97=================================================★ 用受此函数的启发，函数返回值用的 return n == i ? 1 : 0; 很简洁，这种返回值为真或假的函数真就该这么用，而我原来那种用if--else判断的结构相比之下显得有些繁，因此将上面2006.11.19更新中的判断素数函数改写了一下，虽然还是用了两个return 但比原来的看上去要好一些，如下：int prime(int n){    int i;    int k = sqrt(n);    if(n > 1)    {        for(i = 2; i <= k; i++)            if(n % i == 0)                break;                return (i >= k + 1) ? 1 : 0;    }    else        return 0;}

评论