题目描述: 在遥远的魔法王国里,住着一位年轻的魔法师艾莉。她刚刚继承了王国的魔法宝座,为了证明自己的实力,她决定进行一项神奇的仪式。
艾莉在王宫的大厅里排列了n颗魔法宝石,这些宝石最初都是黑色的,代表着王国的各个地区。她要用自己的魔法逐步点亮这些宝石,让它们变成白色,象征着将魔法之光带到王国的每个角落。
仪式规则如下:
第1天:艾莉用魔法点亮第1颗宝石。
第2天:她点亮所有序号是2的倍数的宝石。
第3天:她点亮所有序号是3的倍数的宝石。
以此类推,第k天她会点亮所有序号是k的倍数的宝石。
王国的智者们很好奇: 艾莉最少需要多少天才能点亮所有的宝石? 最后一颗宝石(第n颗)会在第几天被点亮?
我的代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 10000005;
int cnt=0,lstd,mxds;
int st[N],primes[N];
void ola(long long);
int maxprim (long long n){
ola(n);
return primes[cnt];
}
void ola(long long n)
{
for (int i = 2; i <= n; i++ )
{
if (st[i] == 0) primes[++cnt] = i;//将质数存到primes中
for (int j = 0; primes[j]*i <= n; j++)//要确保质数的第i倍是小于等于n的。
{
st[primes[j] * i] = 1;
if (i % primes[j] == 0) break;
}
}
}
int main(){
long long n;
cin>>n;
lstd=n;
for(int i=2;i*i<=n;i++){
if(n%i==0){
lstd=i;
break;
}
}
mxds=maxprim(n);
printf("%d %d\n",mxds,lstd);
return 0;
}
在输入9999991之后直接runtime error 5:floating point exeption