题目47：找出最小的具有四个不同质数因子的四个连续整数

欧拉计划

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:



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

最小的三个具有三个不同质数因子的连续整数是：



找出最小的四个具有四个不同质数因子的整数。它们之中的第一个是多少？

迷雾少年

怎么我出来了好多。。
16:2 2 2 2
24:2 2 2 3
36:2 2 3 3
40:2 2 2 5
54:2 3 3 3
56:2 2 2 7
60:2 2 3 5
81:3 3 3 3
84:2 2 3 7
88:2 2 2 11
90:2 3 3 5
100:2 2 5 5
104:2 2 2 13
126:2 3 3 7
..........

#include "myLib\\myLib.h"
#include <vector>
#pragma  comment(lib,"myLib\\myLib.lib")

//分解质因数并且那啥
bool div(int n)
{
        vector<int> result;
        int num = 0;
        int t = n;
        while (1!=n)
        {
                for (int i =2;i<=n;i++)
                {
                        if(n%i==0)
                        {
                                //i就是其中一个因数
                                //如果有一个因数不是质数 false
                                if(!iszhishu(i))
                                        return false;
                                result.push_back(i);
                                num++;

                                if(num>4)//超过4个质因数了 咋办
                                        return false;

                                n/=i;
                                i=1;

                        }
                }
        }
        if(num!=4) return false;

        std::cout<<t<<":";
        for (int k=0;k<result.size();k++)
        {
                std::cout<<result[k]<<" ";
        }
        std::cout<<endl;
        return true;

}
int main(void)
{
        
    for (int i = 1;i<10000;i++)
    {
                div(i);
                  
    }
        return 0;
}

迷雾少年

iszhishu 是个判断是否质数的函数 没带上

jerryxjr1220

迷雾少年 发表于 2016-8-30 21:56
怎么我出来了好多。。
16:2 2 2 2
24:2 2 2 3

看错题目，是4个连续数字，不是3个。
答案应该是134043

class henum:
    def __init__(self,num):
        henum.num = 0
        henum.yue = []

def yueshu(num):
    yuelist = []
    for i in range(2,int(num**0.5+1)):
        if isPrime(i):
            if num%i == 0:
                yuelist.append(i)
                num1 = int(num/i)
                if isPrime(num1):
                    yuelist.append(num1)
                else:
                    yuelist = yuelist + yueshu(num1)
    return yuelist

def isPrime(num):
    flag = 1
    if num == 2:
        return flag
    elif num % 2 == 0:
        flag = 0
        return flag
    else:
        for i in range(3,int(num**0.5+1),2):
            if num % i == 0:
                flag = 0
                break
        return flag

hnumlist = []
for j in range(100000,200000):
    if isPrime(j) == 0:
        h=henum(j)
        h.num = j
        h.yue = list(set(yueshu(j)))
        hnumlist.append(h)

for k in range(3,len(hnumlist)):
    if hnumlist[k-3].num == hnumlist[k-2].num -1 and hnumlist[k-2].num == hnumlist[k-1].num -1 and hnumlist[k-1].num == hnumlist[k].num -1:
        if len(hnumlist[k-3].yue) == 4 and len(hnumlist[k-2].yue) == 4 and len(hnumlist[k-1].yue) == 4 and len(hnumlist[k].yue) == 4:
                print(hnumlist[k-3].num, hnumlist[k-3].yue)
                break

芒果加黄桃

# encoding:utf-8
# 找出最小的不能写作一个质数与一个平方数的二倍之和的奇合数
from time import time 
from math import sqrt
def getPrimes(N):
    primes = [True] * N
    primes[0], primes[1] = False, False
    for i, prime in enumerate(primes):
        if prime:
            for j in range(i * i, N, i):
                primes[j] = False
    return [k for k, p in enumerate(primes) if p]
def findPrimeFactors(n, l_pr, s_pr):
    if n in s_pr:
        return [n]
    sqr_n = int(sqrt(n)) + 1
    result = list()
    for pr in l_pr:
        if n % pr == 0:
            result.append(pr)
            result.extend(findPrimeFactors(int(n / pr), l_pr, s_pr))
            break
        if pr > sqr_n:
            break
    return result
def euler047(N=150000):
    l_primes = getPrimes(N)
    s_primes = set(l_primes)
    l_result = dict()
    for each in range(647, N):
        tmp = findPrimeFactors(each, l_primes, s_primes)
        if len(set(tmp)) == 4:
            l_result[each] = tmp
        else:
            l_result.clear()
        if len(l_result) == 4:
            print(l_result)
            break
if __name__ == '__main__':
    start = time() 
    euler047()
    print('cost %.6f sec' % (time() - start))

{134043: [3, 7, 13, 491], 134044: [2, 2, 23, 31, 47], 134045: [5, 17, 19, 83], 134046: [2, 3, 3, 11, 677]}
cost 0.955096 sec

愤怒的大头菇

import math


def Prime(x):
    if x > 1:
        if x == 2:
            return True
        if x % 2 == 0:
            return False
        for i in range(3, int(math.sqrt(x)+1), 2):
            if x % i == 0:
                return False
        return True


def cycle(a):
    list1 = []
    while True:
        tmp = a
        i = 2
        while True:
            if Prime(i):
                if tmp % i == 0:
                    if i not in list1:
                        list1.append(i)
                    tmp = tmp/i
                    i = 2
                    continue
                elif Prime(tmp) or tmp == 1:
                    if tmp not in list1:
                        if Prime(tmp):
                            list1.append(tmp)
                    return list1
                else:
                    i += 1
            else:
                i += 1


i = 2
while True:
    if not Prime(i):
        if len(cycle(i)) == 4 and len(cycle(i+1)) == 4 and len(cycle(i+2)) == 4 and len(cycle(i+3)) == 4:
            print(i)
            break
        else:
            i += 1
    else:
        i += 1

答案:134043

渡风

此代码使用matlab编程
Problem47所用时间为691.2743秒
Problem47的答案为134043

%% Problem47.m
%最后编辑时间：2017-06-13 13:16 版本1.0
%找出连续四个数，四个数的没有相同的质因子，输出它们中的第一个

% Problem47所用时间为691.2743秒
% Problem47的答案为134043

function Output = Problem47()
tic

Start = 644;
Meet = 0;
process = 1;
while (Meet == 0)
    Meet = 1;
    Start = Start + process;
    disp(Start)
    AllNum = Start : Start + 3;
    for ii = 1:4
        if Isprime(AllNum(ii)) == 1 
            process = ii;
            Meet = 0;
            break
        else
            if RealFactorNum(AllNum(ii)) < 4
               process = ii;
               Meet = 0;
               break
            end
        end
    end      
end

Output = AllNum(1);
toc

disp('此代码使用matlab编程')
disp(['Problem47所用时间为',num2str(toc),'秒'])
disp(['Problem47的答案为',num2str(Output)])
end
%% Isprime.m
%判定一个数是否为质数
function Judge = Isprime(n)
if nargin == 0
    n = 64;
end

if n == 2
    Judge = 1;
else
    if mod(n,2) == 0
        Judge = 0;
    else
        Judge = 1;
        for ii = 3: 2 :floor(sqrt(n)) + 1
            if mod(n,ii) == 0
                Judge = 0;
                break
            end
        end
    end
end
end

%% 输入一个数得到其真因子的个数
% 若输入为质数，则返回0
function Output = RealFactorNum(n)
if nargin == 0
n = 64;
end
% if isprime(n) == 1
%     Output = 0;
% else
%    PossiFactor = 1:n-1;
    Judge = ones(1,n-1);
    Judge(1) = 0;
    for ii = 1:n-1
        if Judge(ii) == 1
            for jj = 2*ii : ii : n-1
                Judge(jj) = 0;
            end
        end
    end
    PossiFactor = find(Judge == 1);
    PrimeFactor = [];
    while (isprime(n) == 0)
        for kk = 1:length(PossiFactor)
            if mod(n, PossiFactor(kk)) == 0
                PrimeFactor = [PrimeFactor, PossiFactor(kk)];
                n = n/PossiFactor(kk);
                break
            end
        end
    end
    PrimeFactor = [PrimeFactor, n];
    Output = length(unique(PrimeFactor));
end
    
    

najin

用的matlab：
结果是：
      134043

时间已过 4.581318 秒。
>>

zzzgod

#include <iostream>
#include <cmath>

using namespace std;

bool div(int num)
{
        int count=0;
        for(int i=2;i<=num;i++)
        {
                if(num%i==0)
                {
                        num/=i;
                        count++;
                        while(num%i==0)
                                num/=i;
                } 
                if(count==5)
                        return false;
        }
        if(count==4)
                return true;
        return false;
} 

int main()
{
        int count=0;
        for(int i=2;i<=100000000;i++)
        {
                if(div(i))
                        count++;
                else
                        count=0;
                if(count==4)
                {
                        cout<<i-3;
                        return 0;
                } 
        }
}

k往事如烟k

134043

def isPrime(num):
    if num <= 1:
        return False
    else:
        for i in range(2, int(num**0.5+1)):
            if num % i == 0:
                return False
        else:
            return True

def PrimeFactorList(num):
    if isPrime(num):
        return []
    else:
        PrimeFactorList = []
        for i in range(2, int(num**0.5+1)):
            while num % i == 0:
                num //= i
                PrimeFactorList.append(i)
                if isPrime(num):
                    PrimeFactorList.append(num)
        return list(set(PrimeFactorList))

for num1 in range(2*3*5*7, 1000000):
    num2 = num1 + 1
    num3 = num1 + 2
    num4 = num1 + 3
    if len(PrimeFactorList(num1)) == 4:
        if len(PrimeFactorList(num2)) == 4:
            if len(PrimeFactorList(num3)) == 4:
                if len(PrimeFactorList(num4)) == 4:
                    print(num1)
                    break

王小召

借用楼上答案， 本题重点：对于大数据查找效率考量，速度从快到慢：set > dict > list 如果本题第16行用 if num in b_nums（也就是：in + list模式） 做替换，用时可能会多百倍，复杂度会从O(log N) 编程了 O(N)！!

结果是：{134043: [3, 7, 13, 491], 134044: [2, 2, 23, 31, 47], 134045: [5, 17, 19, 83], 134046: [2, 3, 3, 11, 677]}
用时：0.6084039 秒

import time


def prime(N):
    bool_num = [1] * N
    bool_num[0], bool_num[1] = 0, 0
    for i, j in enumerate(bool_num):
        if j:
            for x in range(i**2, N, i):
                bool_num[x] = 0
    return [i for i, j in enumerate(bool_num) if j]


def composite_numbers(num, b_nums, s_nums, result = []):
    if num in s_nums:
        result.append(num)
        return [num]

    sqr_n = num**0.5 + 1
    for each_prime in b_nums:
        if not num % each_prime:
            result.append(each_prime)
            composite_numbers(int(num/each_prime), b_nums, s_nums, result)
            break
        elif each_prime > sqr_n:
            break
    return result


def cal_(N):
    b_nums = prime(N)
    s_nums = set(b_nums)
    d_result = {}
    for number in range(647, N):
        tmp = composite_numbers(number, b_nums, s_nums, [])
        if len(set(tmp)) == 4:
            d_result[number] = tmp
        else:
            d_result.clear()
        if len(d_result) == 4:
            return d_result

print("结果是：{}\n用时：{} 秒".format(cal_(150000), time.process_time()))

永恒的蓝色梦想

from time import process_time as t
t1=t()
from itertools import count
def f(a):
  l=set()
  if a%2==0:
    while a%2==0:a//=2
    l.add(2)
  while a!=1:
    for i in range(3,int(a**0.5+1),2):
      if a%i==0:
        while a%i==0:a//=i
        l.add(i)
        break
    else:
      l.add(int(a))
      break
  return len(l)==4
c=count(1)
while 1:
  n=c.__next__()
  if f(n):
    l=n
    for i in range(3):
      if not f(c.__next__()):break
    else:break
print(f'运行结果：{l}\n运行时间：{t()-t1}s')

运行结果：134043
运行时间：0.734375s

永恒的蓝色梦想

王小召 发表于 2019-6-24 14:28
借用楼上答案， 本题重点：对于大数据查找效率考量，速度从快到慢：set > dict > list 如果本题第16行用 if ...

老哥说实话我看不懂你的代码……

debuggerzh

134043

Process returned 0 (0x0)   execution time : 1.258 s
Press any key to continue.

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;

const int M = 5e5;
int cnt = 0;
bool prime[M];
int factor[M];

void euler_sieve(){
  prime[1] = false;
  for (int i = 2;i <= M;i++) prime[i] = true;

  for (int i = 2;i <= M;i++){
    if (prime[i]) factor[++cnt] = i;
    for (int j = 1;j <= cnt && i*factor[j] < M;j++){
      prime[i*factor[j]] = false;
      if (i % factor[j] == 0) break;
    }
  }
}

void solve(int x,set<int> & s){
  for (int i = 1;x != 1;i++){
    while (x % factor[i] == 0){
      s.insert(factor[i]);
      x /= factor[i];
    }
  }
}

bool judge(set<int> s[]){
  for (int i = 0;i < 4;i++)
    if (s[i].size() != 4) return false;

  for (int i = 0;i < 3;i++){
    for (int j = i+1;j < 4;j++){
      if (s[i] == s[j]) return false;
    }
  }
  return true;
}

int main(){
  euler_sieve();

  for (int i = 2;;i++){
    set<int> s[4];
    if (prime[i] || prime[i+1] || prime[i+2] || prime[i+3]) continue;

    for (int j = 0;j < 4;j++) solve(i+j,s[j]);

    if (judge(s)) {cout << i << endl; break;}
  }
  return 0;
}

4444567

#找到一个数的所有质因数，运用元组
#找满足要求的下一个数
#两个列表，一个装质因数，一个装整数，用长度判断
def prime(n):
    if n == 2 or n==3:
        return True
    if n%2==0:
        return False
    else:
        for i in range(3,int(n**0.5)+1,2):
            if n%i==0:
                return False
        return True
    
def zys(n):
    l = []
    for i in range(2,int(n/30)+1):#因为找四个不同质因数，那前三个质因数最小是2、3、5
        if n%i == 0 and prime(i):
            l.append(i)
    return l

n = 647
while n < 150000: 
    if len(zys(n)) ==4:
        if len(zys(n+1)) ==4:
            if len(zys(n+2)) ==4:
                if len(zys(n+3)) ==4:
                    print(n,zys(n))
                    print(n+1,zys(n+1))
                    print(n+2,zys(n+2))
                    print(n+3,zys(n+3))
                    break
    n += 1

    

是有点菜，但是幸好可以算出来

a1351468657

迷雾少年 发表于 2016-8-30 21:56
怎么我出来了好多。。
16:2 2 2 2
24:2 2 2 3

你再看看题目

a1351468657

#include <stdio.h>
#include <time.h>

int check_num(int);
int check_num(int num)//判断是否有四个不同的质数因子
{
        int i, j, k, count = 0;
        k = num;
        for (i = 2; i <= num / 2; i++)
        {
                if (k % i == 0)
                {
                        count++;
                }
                while (k % i == 0)
                {
                        k /= i;
                }                
        }
        if (count == 4)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}

main()
{
        int i = 644, j;
        int begin = time(NULL), end;

        while (1)
        {
                i++;
                j = i;
                if (check_num(j))
                {
                        if (check_num(++j))
                        {
                                if (check_num(++j))
                                {
                                        if (check_num(++j))
                                        {
                                                printf("%d\n", i);
                                                break;
                                        }
                                }
                        }
                }
                
        }
        end = time(NULL);
        printf("time = %ds", end - begin);
}

134043
time = 28s

guosl

/*
欧拉问题47
答案：134043
耗时：0.0228895秒
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const int INF = 0x7fffffff;
const int nSteps = 1000;

bool chkpcount(int n)//计算n中的素因数的个数是否是4
{
  if (n == 1 || n == 2)
    return false;
  int nCount = 0;//记录素因数的个数
  if (n % 2 == 0)
  {
    ++nCount;
    while (n % 2 == 0)
      n /= 2;
  }
  int k = 3;
  while (n > 1 && nCount <= 4)
  {
    int d = (int)sqrt((double)n);
    bool bFlag = true;
    for (; k <= d; k += 2)//找出当前n的最小素因数
    {
      if ((n % k) == 0)//找到一个比n小的素因数
      {
        bFlag = false;
        ++nCount;
        while (n % k == 0)//将n中的所有因数k除掉
          n /= k;
        break;
      }
    }
    if (bFlag)//没有找到比n小的素因数，故n本身是一个素数
    {
      ++nCount;
      break;
    }
  }
  return (nCount == 4);
}

int main(void)
{
  char p[nSteps + 5];
  int k = 647;
  int nResult = INF;
  p[nSteps + 4] = 0;
  while (true)
  {
    memset(p, '0', (nSteps + 4) * sizeof(char));
    for (int i = 0; i < nSteps + 4; ++i)//+4是为了解决前后重叠的问题
    {
      int j = i + k;
      if (chkpcount(j))
        p[i] = '1';//标记哪些数是有4个素数因数
    }
    char* pi = strstr(p, "1111");//查找是否有4个连续的存在
    if (pi != NULL)//存在
    {
      int ip = int(pi - p) + k;
      nResult = min(nResult, ip);//记录
      break;//退出循环
    }
    else
      k += nSteps;
  }
  cout << nResult << endl;
  return 0;
}

叶落了

#利用一个数可以表示唯一的质数积形式，迭代后看范围类是否只有4个质数满足
#include<stdio.h>
#include<math.h>

int determine0(int i)
{
        int l;
        l=pow(i,0.5);
        for(int m=2;m<=l;m++)
        {
                if(i%m==0)
                {
                        return 0;
                }
        }
        return 1;
}

int determine1(int i)
{
        int num=0;
        //int k=pow(i,0.5);
        int k=i/30;
        for(int m=2;m<=k;m++)//for(int m=2;m<=k;m++)想错了，这里的范围弄错  了
        {
                if(determine0(m)&&i%m==0)
                {
                        num=num+1;
                        if(num>4)
                        {
                                return 0;
                        }
                }
        }
        if(num==4)
        {
                return 1;
        }
        return 0;
}
int main(void)
{
        int i=1;
        int x=100;
        while(i)
        {
                if(determine1(x)&&determine1(x+1)&&determine1(x+2)&&determine1(x+3))
                {
                        i=0;
                        printf("%d\n",x);
                }
                x=x+1;
        }
        return 0;
}