源.cpp

#include <iostream>
#include "PrimeNumber.h"
using namespace std;

int main()
{
	cout << "----------求2—x范围内的素数----------" << endl << endl;
	
	int x;
	cout << "请输入边界x：";
	cin >> x;
	
	cout << endl << "2-" << x << "中所有的素数为：" << endl;

	f1(x);	//常规做法
	//f2(x);	//埃拉托色尼筛选法
	
	cout << endl << endl;
	system("pause");
	return 0;
}

PrimeNumber.h

#ifndef PrimeNumber_h
#define PrimeNumber_h

void f1(int);	//常规做法
void f2(int);	//埃拉托色尼筛选法

#endif

PrimeNumber.cpp

#include <iostream>
#include "PrimeNumber.h"
using namespace std;

void f1(int x)	//常规做法（已优化）
{
	bool judge;
	int k = 4;	//对应着2、3、5、7这4个数
	cout << "2 3 5 7 ";

	for (int i = 11; i <= x; i = i + 2)	//i每次加2，排除掉2的倍数
	{
		judge = true;	//重置输出的判断条件

		//排除掉3、5、7的倍数，因为逢10里必至少有一个
		if ((i % 3 == 0) | (i % 5 == 0) | (i % 7 == 0)) continue;

		for (int j = 11; j*j <= i; j = j + 2)	//把开方运算换成平方运算，运算速度加快
		{
			if (i%j == 0)
			{
				judge = false;
				break;
			}
		}

		if (judge == true)	//i不能被任何数整除，故输出
		{
			cout << i << " ";
			k = k + 1;
			if (k % 10 == 0) cout << "\n";	//10个就换行
		}
			
	}

	cout << endl << endl << "共" << k << "个素数";
}

void f2(int x)	//埃拉托色尼筛选法
{
	int *a = new int[x - 1];
	int i, j;

	for (i = 0; i < x - 1; ++i) a[i] = i + 2;   //赋值  

	for (j = 0; j < x - 1; ++j)
	{
		if (a[j] != 1)
		{
			//去掉tmp的倍数（即赋值为1）  
			for (i = j + 1; i < x - 1; ++i)
			{
				if (a[i] % a[j] == 0) a[i] = 1;
			}
		}
	}

	for (i = 0, j = 0; i < x - 1; ++i)
	{
		if (a[i] != 1)
		{
			cout << a[i] << " ";
			j = j + 1;
			if (j % 10 == 0) cout << "\n";	//10个就换行
		}
	}

	cout << endl << endl << "共" << j << "个素数";
}