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）acutus (mail: acutus@126.com) // 博客地址：http://www.cnblogs.com/acutus/ #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; }
|
Answer: |
134043 |
（Problem 47）Distinct primes factors
原文：http://www.cnblogs.com/acutus/p/3547901.html