# 数学--数论--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;
}```

0 条评论

• ### 数学--数论--HDU2136 Largest prime factor 线性筛法变形

问数的编号，素数的话就是第几个素数就是他的编号如 2-1 3-2 5-3 7-4非素数就是最小的素因子的序号是他的序号。修改后的线筛完事。

• ### 网络流--最大流--POJ 1273 Drainage Ditches

Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite...

• ### POJ2236 （并查集）

An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical te...

• ### Codeforces 626F Group Projects(滚动数组+差分dp)

F. Group Projects time limit per test：2 seconds memory limit per test：256 megaby...

• ### 开发工具总结（6）之Android Studio模板配置详解(提高开发效率必备技能)

版权声明：本文为博主原创文章(部分引用他人博文，已加上引用说明)，未经博主允许不得转载。https://www.jianshu.com/p/1fe87050c1...

• ### 算法细节系列（17）：有向环检测&&拓扑排序

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### Leetcode 137. 只出现一次的数字 II - 题解

https://leetcode.com/problems/single-number-ii/