(Hdu Acm Step 2.1.3)Largest prime factor

电玩女神 2022-06-10 07:15 106阅读 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 条评论，106人围观）

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

相关阅读

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

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

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

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

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

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

相关 1059. Prime Factors (25)

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

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