算法训练 Torry的困惑(基本型)

问题描述

Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7……这样的数叫做质数。Torry突然想到一个问题，前10、100、1000、10000……个质数的乘积是多少呢？他把这个问题告诉老师。老师愣住了，一时回答不出来。于是Torry求助于会编程的你，请你算出前n个质数的乘积。不过，考虑到你才接触编程不久，Torry只要你算出这个数模上50000的值。

输入格式

仅包含一个正整数n，其中n<=100000。

输出格式

输出一行，即前n个质数的乘积模50000的值。

样例输入

1

样例输出

2

快速求素数的算法

#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;
}