一、模板
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;
}