2015/04/14

【UVa】294-Divisors (質數表+質因數分解)




題目連結

植樹表及質因數相關分解,請見
http://celinechiu0809.blogspot.tw/2015/04/c-sieve-mrthod.html

題目大意
給一個範圍L, U,不大於int範圍。U-L <= 10000
找出在這個範圍內擁有最多因數的數。

解題思路
先建質數表,後直因數分解

Code

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdlib>
#include <cstdio>
#include <cmath>
 
using namespace std;
 
int ans, divisor;
bool is_prime[40000];
 
void build_prime_tb(){
    /*是質數:false, 不是質數:true*/
    is_prime[0] = is_prime[1] = true;
    for (int  i = 2; i <= sqrt(40000); i++) {
        if (!is_prime[i]) {
            for (int k=39999/i, j=i*k; k>=i; k--, j-=i) {
                if (!is_prime[k]) is_prime[j] = true;
            }
        }
    }
}
 
void prime_factor(int num){ /*質因數分解*/
    int m = (int)(sqrt(num)+0.001);
    int x = num;
    int tmp=1, ppow;
    for (int i=2; i<=m; i++){
        ppow = 0;
        if(!is_prime[i] && x%i==0){
            ppow=0;
            while (x%i==0){
                x /= i;
                ppow++;
            }
            tmp *= ppow+1;
        }
    }
    if (x>1) tmp *= 2;
    if (tmp > divisor) divisor=tmp, ans=num;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    build_prime_tb();
    while (n--){
        int range_low, range_high;
        scanf("%d %d", &range_low, &range_high);
        ans = 0, divisor=0;
        for (int i=range_low; i<=range_high; i++)
            prime_factor(i);
        printf("Between %d and %d, %d has a maximum of %d divisors.\n", range_low, range_high, ans, divisor);
    }
    return 0;
}