HDU 2136 Largest prime factor（素数筛法）

柔情只为你懂 2024-02-17 19:44 16阅读 0赞

## Largest prime factor ##

**Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 12087 Accepted Submission(s): 4290**

Problem Description

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

题意：每一个素数都对应一个序号，比如说1对应0，2对应1，3对应2，5对应3,；现在给你一个数n，要你找出最大质因数对应的序号。

思路：素数筛法求解；先用素数筛法打表，对每一个素数，把它以及它的倍数都标上序号，当输入n时，直接打印即可。

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=1e6+5;
    int save[maxn];
    int main(){
    	memset(save,0,sizeof(save));
    	int cnt=1;
    	save[1]=0;
    	for(int i=2;i<maxn;i++){
    		if(!save[i]){
    			for(int j=i;j<maxn;j+=i)
    			save[j]=cnt;
    			
    			cnt++;
    		}
    	}
    	
    	int n;
    	while(scanf("%d",&n)==1){
    		printf("%d\n",save[n]);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，16人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 2136 Largest prime factor（素数筛法）

Largest prime factor Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768

柔情只为你懂/ 2024年02月17日 19:44/ 0 赞/ 17 阅读

相关【hdoj2136】Largest prime factor

Largest prime factor Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768

喜欢ヅ旅行/ 2022年07月15日 01:40/ 0 赞/ 68 阅读

相关【hdoj2136】Largest prime factor

Largest prime factor Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768

比眉伴天荒/ 2022年07月15日 01:40/ 0 赞/ 73 阅读

相关 Largest prime factor HDU - 2136

Largest prime factor HDU - 2136 -------------------- Problem Everybody knows any

比眉伴天荒/ 2022年06月14日 10:43/ 0 赞/ 118 阅读

相关 Prime Gap UVA - 1644——筛法建素数表

Think: 1题意：输入一个整数n，输出后一个素数和前一个素数的差值，输入是素数时输出0，n不超过1299709（第100000个素数），输入0时结束不进行操作 2方

￡神魔★判官ぃ/ 2022年06月14日 04:39/ 0 赞/ 127 阅读

相关 (Hdu Acm Step 2.1.3)Largest prime factor

题目： Everybody knows any number can be combined by the prime number. Now, your task i

电玩女神/ 2022年06月10日 07:15/ 0 赞/ 75 阅读

相关 POJ - 3518 - Prime Gap（筛素数）

给出一个数字n，求n所在得一个区间的长度，区间是最近的两个素数为边界；那么n如果为素数的话，那么直接输出0；先打表，因为用的是前10万个素数，所以在打表的时候，记录素数

桃扇骨/ 2022年06月08日 11:20/ 0 赞/ 118 阅读

相关素数筛法

//暴力枚举素数筛法 o(n 根号n) for(int i=2;i<=n;i++){ bool g=0; for(int j=2;jj<

╰+哭是因爲堅強的太久メ/ 2022年04月04日 10:54/ 0 赞/ 231 阅读

相关 PAT甲级1059 Prime Factors (25)（素数筛+求一个数的质因子）

Prime Factors 题目描述 Given any positive integer N, you are supposed to find all

迈不过友情╰/ 2021年12月03日 11:04/ 0 赞/ 238 阅读

相关 HDU - 2710 - Max Factor【筛法求素数】题解

目录 1.题目 2.代码 1.题目 To improve the organization of his f

电玩女神/ 2021年07月24日 23:07/ 0 赞/ 357 阅读