<谭> 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) [更新] 2006.11.18 [066] 筛选法求素数
[更新] 2006.11.19
{
printf("%d ", m);
n = n + 1;
}
if (n % 10 == 0)
printf("\n");
}
printf("\n");
return 0;
}
★ 用筛选法也可以做, 下章数组再续。
★ 一个自然数是素数,且它的各位数字位置经过任意对换后仍为素数,则称是绝对素数。
#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 29
31 37 41 43 47 53 59 61 67 71
73 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 29
31 37 41 43 47 53 59 61 67 71
73 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;
}
评论