一、模板

const int SIZE = 1200;// 筛1-1200中的素数
bool isComp[SIZE] = { false };// 是否为合数
int P[SIZE] = { 0 };			// 素数
int PCnt = 0;					// 素数个数

void sieve() {
	for (int i = 2; i < SIZE; ++i) {
		if (!isComp[i]) P[PCnt++] = i;

		for (int j = 0; j < PCnt&&i*P[j] < SIZE; ++j) {
			isComp[i*P[j]] = true;
			if (0 == i % P[j]) break;
		}
	}
}
bool isPrime(int x) {
	if (x < SIZE) return !isComp[x];
	for (int i = 0; P[i] * P[i] <= x && i < PCnt; ++i)
		if (0 == x % P[i])
			return false;
	return true;
}

二、例题

Solution

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;


const int SIZE = 1200;
bool isComp[SIZE] = { false };
int P[SIZE] = { 0 };
int PCnt = 0;
int ret[SIZE*1000];
void sieve(){
	for (int i = 2; i<SIZE; ++i){
		if (!isComp[i]) P[PCnt++] = i;

		for (int j = 0; j<PCnt&&i*P[j]<SIZE; ++j){
			isComp[i*P[j]] = true;
			if (0 == i % P[j]) break;
		}
	}
}

bool isPrime(int x){
	if (x < SIZE) return !isComp[x];
	for (int i = 0; P[i] * P[i] <= x&&i < PCnt; ++i)
	if (0 == x % P[i])
		return false;
	return true;
}
void solve(int i){
	if (isPrime(i)) ++ret[i];
	else for (int j = 0; j < SIZE && i; ++j){
		if (i % P[j] == 0) { ++ret[P[j]]; solve(i / P[j]); break; }
	}
}
int main()
{
	sieve();
	int n;
	cin >> n;
	for (int i = 2; i <= n; ++i){
		solve(i);
	}
	for (int i = 2; i < SIZE * 1000; ++i){
		if (ret[i]) printf("%d %d\n",i,ret[i]);
	}
	
	return 0;
}