# 工学1号馆

home

## Project Euler 47–Distinct primes factors

Wu Yudong    August 20, 2018     欧拉计划   629

Distinct primes factors

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 = 22 × 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 = 22 × 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）wu yudong
// 博客地址：http://www.wuyudong.com

#include<stdio.h>
#include<stdbool.h>

int a[1002];

bool prim(int n)
{
int i;
for(i = 2; i * i <= n; i++) {
if(n % i == 0)  return false;
}
return true;
}

void init()
{
int i,j;
i = 3;
j = 1;
a[0] = 2;
while(j < 1000) {
if(prim(i)) a[j++] = i;
i += 2;
}
}

bool judge(int n)
{
int i, flag, count;
count = flag = 0;

for(i = 0; i < 1000; i++) {
while(n % a[i] == 0) {
flag = 1;
n = n / a[i];
}
if(flag) count++;
flag = 0;
if(count == 4) return true;
}
return false;
}

void solve()
{
int i;
for(i = 20; i < 1000000;) {
if(judge(i)) {
if(judge(i + 1)) {
if(judge(i + 2)){
if(judge(i + 3)){
printf("%d %d %d %d\n", i, i + 1, i + 2, i + 3);
return;
} else {
i += 4;
continue;
}
} else {
i += 3;
continue;
}
} else {
i += 2;
continue;
}
} else {
i++;
}
}
}

int main()
{
init();
solve();
return 0;
}