本题要求统计给定整数M和N区间内素数的个数并对它们求和。
输入格式:
输入在一行中给出两个正整数M和N(1≤M≤N≤500)。
输出格式:
在一行中顺序输出M和N区间内素数的个数以及它们的和,数字间以空格分隔。
输入样例:
10 31
输出样例:
7 143
方法一不易理解,但是是我从课本上摘录的求素数很好的一个方法。据说数学上可以证明,检查素数只要看取余到它的根号就行。
方法一:
#include <stdio.h>#include <math.h>int isPrime (int x) {int i, ret;if (x < 2)ret = 0;else {for (i = 2; i < sqrt(x); i++)if (x % i == 0)break;if (i > sqrt(x))ret = 1;elseret = 0;}return ret;}int main(void){int M, N, i, count, sum;count = sum = 0;scanf("%d %d", &M, &N);for (i = M; i <= N; i++) {if (isPrime(i)){count++;sum += i;}}printf("%d %d", count, sum);return 0;}
方法二:规规矩矩的方法,但是时间复杂度高一些。
#include <stdio.h>int isPrime (int x) {int i, ret;if (x < 2)ret = 0; //0、1等不是素数。else {for (i = 2; i < x; i++) //素数:除了1和它本身才能除尽的数。if (x % i == 0)break;if (i == x)ret = 1;elseret = 0;}return ret;}int main(void){int M, N, i, count, sum;count = sum = 0;scanf("%d %d", &M, &N);for (i = M; i <= N; i++) {if (isPrime(i)){count++;sum += i;}}printf("%d %d", count, sum);return 0;}