素数&构造

牛客网2019寒训2

题目描述

处女座进行了一场c语言的考试，要求很简单，输出2000个正整数，并且满足以下条件：
1.任意两个数互质
2.任意两个数x,y，满足，其中为n的因子的个数
举例：6的因子有1，2，3，6，所以

输入描述:

本题没有输入

输出描述:

2000行，每行一个正整数
输出的每个整数都必须在1-4*108之间
如果有多组答案，输出任意一组即可。

思路：
两个质数相乘得到的数a和另外两个不同的质数相乘得到的数b，a与b互质。
是积性函数,x,y 互质,有
只需保证即可，找出前4000个质数构造即可。取第 1个质数和第 4000 个质数相乘得第一个答案，取第 2个质数和第 3999 个质数相乘得第二个答案 ……并保证最大的数在 4e8 以内 。
用排列组合证明，4个互异的质数，共有个因数，所有只要筛出不少于4000个质数，然后两两组合即可。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 4e6;  //太大会爆内存
  
int prime[5000];
bool isprime[N+100];
int cnt;
  
void isPrime()  //欧拉筛
{
    memset(isprime, true, sizeof(isprime));  //把所有数字都初始化为素数
    cnt = 0;
    isprime[0] = isprime[1] = false;
    for(int i = 2; i<N; ++i)  //遍历N以内的数
    {
        if(isprime[i]) prime[cnt++] = i; //i是素数，储存素数
        for(int j = 0; j<cnt && i*prime[j]<N; ++j) //利用素数相乘，筛掉不是素数的合数
        {
            isprime[i*prime[j]] = false;
            if(i % prime[j] == 0) break;  //保证了每个合数只会被它的最小素因子筛掉
        }
        if(cnt > 4010)  return ;  //要放在里面，不然会出现负数。。？？
    }
  
}
  
int main()
{
    //freopen("debug\\in.txt","r",stdin); //输入重定向，输入数据将从in.txt文件中读取
    //freopen("ouput.txt", "w", stdout);  //输出重定向，输出数据将保存在out.txt文件中
    isPrime();
    cnt--;
    for(int i=0; i<2000; i++, cnt--)
        printf("%d\n", prime[i]*prime[cnt]);
    return 0;
}