The first two consecutive numbers to have two distinct prime factors are:
14 = 2 7 15 = 3
5
The first three consecutive numbers to have three distinct prime factors are:
644 = 2² 7
23 645 = 3
5
43 646 = 2
17
19.
Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?
题目大意：
最小的两个具有两个不同质数因子的连续整数是：
14 = 2 7 15 = 3
5
最小的三个具有三个不同质数因子的连续整数是：
644 = 2² 7
23 645 = 3
5
43 646 = 2
17
19.
找出最小的四个具有四个不同质数因子的连续整数。它们之中的第一个是多少？
//（Problem 47）Distinct primes factors
// Completed on Thu, 13 Feb 2014, 12:50
// Language: C11
//
// 版权所有（C）acutus (mail: acutus@126.com)
// 博客地址：http://www.cnblogs.com/acutus/ #include<stdio.h>
#include<stdbool.h> int a[]; bool prim(int n)
{
int i;
for(i = ; i * i <= n; i++) {
if(n % i == ) return false;
}
return true;
} void init()
{
int i,j;
i = ;
j = ;
a[] = ;
while(j < ) {
if(prim(i)) a[j++] = i;
i += ;
}
} bool judge(int n)
{
int i, flag, count;
count = flag = ; for(i = ; i < ; i++) {
while(n % a[i] == ) {
flag = ;
n = n / a[i];
}
if(flag) count++;
flag = ;
if(count == ) return true;
}
return false;
} void solve()
{
int i;
for(i = ; i < ;) {
if(judge(i)) {
if(judge(i + )) {
if(judge(i + )){
if(judge(i + )){
printf("%d %d %d %d\n", i, i + , i + , i + );
return;
} else {
i += ;
continue;
}
} else {
i += ;
continue;
}
} else {
i += ;
continue;
}
} else {
i++;
}
}
} int main()
{
init();
solve();
return ;
}
|
Answer:
|
134043 |