【hdoj2136】Largest prime factor

喜欢ヅ旅行 2022-07-15 01:40 105阅读 0赞

# Largest prime factor #

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

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

Author

Wiskey

Source

[HDU 2007-11 Programming Contest\_WarmUp][HDU 2007-11 Programming Contest_WarmUp]

Recommend

威士忌

打表法求一个数的质因数在质数序列中的位置。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int MAXN = 1000010;
    int vis[MAXN];
    void getvis() {
    	int k=1;
    	for(int i=2; i<=MAXN; i++) {
    		if(!vis[i]) {
    			vis[i]=k;
    			for(int j=i+i; j<=MAXN; j+=i) {
    				vis[j]=k;
    			}
    			k++;
    		}
    	}
    }
    int main() {
    	getvis();
    	int n;
    	while(scanf("%d",&n)!=EOF) {
    		printf("%d\n",vis[n]);
    	}
    	return 0;
    }

[HDU 2007-11 Programming Contest_WarmUp]: http://acm.hdu.edu.cn/search.php?field=problem&key=HDU+2007-11++Programming+Contest_WarmUp&source=1&searchmode=source

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 68 阅读

相关 JAG Asia 2017 C-----Prime-Factor Prime(素数区间筛)

C: Prime-Factor Prime 时间限制: 1 Sec 内存限制: 128 MB 题目描述 A positive integer is called

Bertha 。/ 2023年06月05日 12:33/ 0 赞/ 31 阅读

相关 Problem 47 Distinct primes factors （分解因子）

Distinct primes factors Problem 47 The first two consecutive numbers to have two d

傷城~/ 2022年07月15日 03:22/ 0 赞/ 185 阅读

相关【hdoj2136】Largest prime factor

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

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

相关【hdoj2136】Largest prime factor

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

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

相关 Largest prime factor HDU - 2136

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

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

相关 (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 赞/ 106 阅读

相关 1059. Prime Factors (25)

Given any positive integer N, you are supposed to find all of its prime factors, and wri

浅浅的花香味﹌/ 2022年05月31日 13:48/ 0 赞/ 231 阅读

相关 (PAT 1059) Prime Factors (分解质因子)

Given any positive integer N, you are supposed to find all of its prime factors, and wri

向右看齐/ 2022年03月18日 02:48/ 0 赞/ 248 阅读

相关 1059. Prime Factors (25)

注意n=n这种情况 // 1059.cpp : 定义控制台应用程序的入口点。 // include<iostream> include<que

雨点打透心脏的1/2处/ 2021年11月22日 04:56/ 0 赞/ 198 阅读