1485: 蓝桥杯算法提高VIP-Torry的困惑(提高型)

解题思路:由找素数演进而来

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<math.h>
using namespace std;
typedef long long LL;
  
bool isprime(LL num) {
    if (num < 2) return false;
    for (int i = 2; i > start >> end;
    if (end < 2)
        cout << 0 << endl;
    else {
        if (start < 2)
            start = 2;
  
        LL limits = (LL)sqrt((double)end);//开根号
        for (LL i = 2; i  2 ? start / i : 2;//i从2开始增大，为了使（N*i从start开始，减少多余计算）（若start<=4时取2，不影响对素数判断）
                for (; N*i = start)
                        primetable[N*i - start] = true;//合数一定能由一个素数和另一个数相乘得到
            }//所以N*i是合数，N*i - start是其所在区间位置
  
        int total = 0;
        for (LL i = 0; i <= end - start; i++)
            if (!primetable[i])//为false时素数
                total++;
        cout << total << endl;
    }
}

注意事项:

参考代码:

#include<iostream>
#include<math.h>
using namespace std;
typedef long long  LL; 
bool s(LL i)
{
	int t=0;
	if(i<2) return false;
	else for(t=2;t<=sqrt((double)i);t++)
		if(i%t==0)
			return false;
	return true;
}
bool num[1500000]={false};//150万内约有10万个素数
int main()
{
	
	LL end,i=0,N=0,p=0;
	cin>>end;
	p=sqrt((double)1500000);
	 for(i=2;i<=p;i++)
	{
		if(s(i))
			for(N=2;N*i<=1500000;N++)
				num[N*i-2]=true;
	}//将素数筛选完
	LL total=1,M=0;
	for(i=2;i<=1500000;i++)
		if(!num[i-2])
				{
					M++;
					if(M<=6)
					total=total*i;
					else total=((total%50000)*(i%50000))%50000;//防溢出
					if(M==end)
					break;
				}
	cout<<total<<endl;
}