問題描述
Torry從小喜愛數(shù)學(xué)巷蚪。一天，老師告訴他濒翻，像2屁柏、3、5有送、7……這樣的數(shù)叫做質(zhì)數(shù)淌喻。Torry突然想到一個問題，前10雀摘、100裸删、1000、10000……個質(zhì)數(shù)的乘積是多少呢阵赠？他把這個問題告訴老師涯塔。老師愣住了，一時回答不出來清蚀。于是Torry求助于會編程的你匕荸，請你算出前n個質(zhì)數(shù)的乘積。不過枷邪，考慮到你才接觸編程不久榛搔，Torry只要你算出這個數(shù)模上50000的值。
輸入格式
僅包含一個正整數(shù)n东揣，其中n<=100000践惑。
輸出格式
輸出一行，即前n個質(zhì)數(shù)的乘積模50000的值嘶卧。
樣例輸入
1
樣例輸出
2
快速求素數(shù)的算法
#include <bits/stdc++.h>
#define MAXN 100000
#define mod 50000
using namespace std;
int prime[MAXN];
bool isPrime[MAXN*5];
int n, cnt;
void getPrimes() {
memset(isPrime, true, sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
cnt = 0;
for(int i = 2; i < MAXN*5; i++) {
if(isPrime[i]) {
prime[cnt++] = i;
}
for(int j = 0; j < cnt && i * prime[j] < MAXN*5; j++) {
isPrime[i * prime[j]] = false;
if(!(i % prime[j])) {
break;
}
}
}
}
int main() {
scanf("%d", &n);
getPrimes();
int res = 1;
for(int i = 0; i < n; i++) {
//cout << prime[i] << endl;
res *= prime[i];
res %= mod;
}
printf("%d\n", res);
return 0;
}
