Largest prime factor HDU - 2136

比眉伴天荒 2022-06-14 10:43 160阅读 0赞

### **Largest prime factor HDU - 2136** ###

--------------------

#### **Problem** ####

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

#### ps：巧妙的求素数方法，先打表，后输出 ####

代码如下：

#include<cstdio> 
    #include<cstring> 
    #include<algorithm> 
    #include<string.h> 
    #include<math.h>
    int a[1000000];
    int main()
    {
        int k = 1;  
         memset(a, 0, sizeof(a));
        for(int i = 2; i < 1000000; i++) {
            if(!a[i]) {
                a[i] = k;
                for(int j = i + i; j < 1000000; j += i)
                    a[j] = k;
                k++;
            }
        }
        int n;
        while(~scanf("%d", &n)) printf("%d\n", a[n]);
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关【hdoj2136】Largest prime factor

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

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

相关【hdoj2136】Largest prime factor

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

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

相关 Largest prime factor HDU - 2136

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

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

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

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

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

相关 1059. Prime Factors (25)

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

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