Wu Yudong's Blog

Distinct primes factors

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19Find 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）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;
}