专栏首页CSDN旧文数学--数论--HDU 2136(素数筛选法)

数学--数论--HDU 2136(素数筛选法)

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

#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
const int MAX = 1000000;
int prime[MAX];
int mark[MAX];

void init()
{
    for (int i = 2, n = 1; i < MAX; i++)
    {
        if (!prime[i])
        {
            mark[i] = n++;
            for (int j = i; j < MAX; j = j + i)
                prime[j] = i;
        }
    }
}
int main()
{
    int n;
    init();
    while (~scanf("%d", &n))
    {
        printf("%d\n", mark[prime[n]]);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数学--数论--HDU2136 Largest prime factor 线性筛法变形

    问数的编号,素数的话就是第几个素数就是他的编号如 2-1 3-2 5-3 7-4非素数就是最小的素因子的序号是他的序号。修改后的线筛完事。

    风骨散人Chiam
  • 网络流--最大流--POJ 1273 Drainage Ditches

    Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite...

    风骨散人Chiam
  • POJ 3581 Prime Gap(二分)

    风骨散人Chiam
  • 图像融合之拉普拉斯融合(laplacian blending)

    一棹烟波
  • POJ2236 (并查集)

    An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical te...

    dejavu1zz
  • Codeforces 626F Group Projects(滚动数组+差分dp)

    F. Group Projects time limit per test:2 seconds memory limit per test:256 megaby...

    Angel_Kitty
  • 慕课网Spark SQL日志分析 - 1.Hadoop概述

    http://hadoop.apache.org/ 对于Apache项目来说,projectname.apache.org Hadoop:hadoop.ap...

    Meet相识
  • 开发工具总结(6)之Android Studio模板配置详解(提高开发效率必备技能)

    版权声明:本文为博主原创文章(部分引用他人博文,已加上引用说明),未经博主允许不得转载。https://www.jianshu.com/p/1fe87050c1...

    AWeiLoveAndroid
  • 算法细节系列(17):有向环检测&&拓扑排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • Leetcode 137. 只出现一次的数字 II - 题解

    https://leetcode.com/problems/single-number-ii/

    imath66

扫码关注云+社区

领取腾讯云代金券