腾讯云·社区
数学--数论--HDU 2136（素数筛选法）
Everybody knows any number can be combined by the prime number. Now, your task is telling me what position of the largest prime factor. The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc. Specially, LPF(1) = 0. Input Each line will contain one integer n(0 < n < 1000000). Output Output the LPF(n). Sample Input 1 2 3 4 5 Sample Output 0 1 2 1 3
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
const int MAX = 1000000;
int prime[MAX];
int mark[MAX];
void init()
{
for (int i = 2, n = 1; i < MAX; i++)
{
if (!prime[i])
{
mark[i] = n++;
for (int j = i; j < MAX; j = j + i)
prime[j] = i;
}
}
}
int main()
{
int n;
init();
while (~scanf("%d", &n))
{
printf("%d\n", mark[prime[n]]);
}
return 0;
}本文参与腾讯云自媒体分享计划，欢迎正在阅读的你也加入，一起分享。
相关文章
扫码关注云+社区
领取腾讯云代金券
我来说两句