浙大版《C语言程序设计（第3版）》题目集 练习4-11 统计素数并求和 (20分)_浙大版c语言习题4-11

方法一：

检查素数，取余到它的根号

#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;
        else
            ret = 0;
    }
    return ret;
}
int main()
{
    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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

运行结果如下：

方法二：

普通做法，时间复杂度高

#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;
		else	ret = 0;
	}
	return ret;
}
int main()
{
	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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27