首页 > 其他 > 详细

HDU 2136 Largest prime factor (素数打表。。。)

时间:2016-06-03 21:17:59      阅读:247      评论:0      收藏:0      [点我收藏+]

题意:给你一个数,让你求它的最大因子在素数表的位置。

析:看起来挺简单的题,可是我却WA了一晚上,后来终于明白了,这个第一层循环不是到平方根,

这个题和判断素数不一样,只要明白了这一点,就很简单了。

代码如下:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <map>
#include <cctype>
#include <cmath>

using namespace std;
typedef long long LL;
const int maxn = 1000000 + 5;
int a[maxn];

void init(){
    memset(a, 0, sizeof(a));
    int cnt = 1;
    for(int i = 2; i < maxn; ++i)  if(!a[i]){//这个地方不是sqrt(maxn+0.5)
        a[i] = cnt++;
        for(int j = i + i; j < maxn; j += i)
            a[j] = a[i];//这个是不断更新的。
    }
}

int main(){
    init();
    int n;
    while(~scanf("%d", &n))
        printf("%d\n", a[n]);
    return 0;
}

 

HDU 2136 Largest prime factor (素数打表。。。)

原文:http://www.cnblogs.com/dwtfukgv/p/5557477.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!