(Hdu Acm Step 2.1.3)Largest prime factor

电玩女神 2022-06-10 07:15 75阅读 0赞

题目：  
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  
题目大意：给你一个数，让你求这个数最大质因子在素数中的位置，比如说2的最大质因子是2，位置就是1, 4和8的最大质因子也是2，位置还是1； 3的最大质因子是3，位置是2,6和9最大质因子也是3，位置是2。  
AC代码：

#include<stdio.h>
    #include<string.h>
    #define max 1000001
    int a[max];
    /*同一个数的质因子位置可能被多次复写。
    但是由于是从小到大遍历，
    这就保证了最后一次写入的是该数的最大质因子的位置
    比如说第一次i=2时，a[2],a[4],a[6],a[8],a[10],a[12]最大质因子的位置是1;
    在第二次 i=3时，a[3],a[6],a[9],a[12],最大质因子的位置等于是2, 这时a[6]和a[12]会将第一次的值覆盖 
    */
    int main()
    {
        int n;
        int i,j,count = 1;
        memset(a, 0, sizeof(a));
        a[1] = 0;
        for(i = 2; i < max; i++)
        {
            if(a[i] == 0)
            {
                for(j = i; j < max; j += i)
                    a[j] = count;
                count++;
            }
        }
        while(scanf("%d", &n) != EOF) 
        {
           printf("%d\n", a[n]);
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

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

相关 HDU ACM Steps攻略 ACM Steps的全部内容

原地址：[http://www.byywee.com/page/M0/S607/607452.html][http_www.byywee.com_page_M0_S607_60

我会带着你远行/ 2022年09月27日 06:29/ 0 赞/ 103 阅读

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

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

相关 Largest prime factor HDU - 2136

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

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

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

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

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

相关 1059. Prime Factors (25)

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

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