标签归档:质数

10000以内质数算法(C语言)

质数计算 第一版

判断一个n自然数能否被2, 3, … n-1 整除. 如果它不能被任意一个数整除, 该自然数就是质数.

例如判断13是否是质数

则需要判断13能否被下面任意一个数整除即可
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
因为13无法被其中任意一个数整除, 所有13是一个质数.

接下来判断12是否是质数

判断2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
以为12已经可以被2整除, 所有后面的数不需要继续计算.

10000以内的质数, C语言v1

#include <stdio.h>

int main(void)
{
	int i, no;
	unsigned long counter = 0;    /* 计算乘除的次数 */

	for (no = 2; no <= 10000; no++) {
		for (i = 2; i < no; i++) {
			counter++;
			if (no % i == 0)
				break;
		}
		if (no == i)    // 质数判断方法
			printf("%d\n", no);
	}

	printf("the number of nultiplication and division: %lu\n", counter); // 5775223

	return 0;
}

质数计算 第二版

在程序1中大于2的倍数都不是质数, 比如 4, 6, 8, …

10000以内的质数, C语言v2

#include <stdio.h>

int main(void)
{
	int i, no;
	unsigned long counter = 0;    /* 计算乘除的次数 */

	no = 2;
	printf("%d\n", no++);

	for (; no <= 10000; no += 2) {
		for (i = 2; i < no; i++) {
			counter++;
			if (no % i == 0)
				break;
		}
		if (no == i)    // 质数判断方法
			printf("%d\n", no);
	}

	printf("the number of multiplication and division: %lu\n", counter);    // 5770224

	return 0;
}

与第一版相比, 乘除次数几乎一致, 因为每一次循环都跳过了除以2这个数字

继续阅读