题目47：找出最小的具有四个不同质数因子的四个连续整数
本帖最后由 欧拉计划 于 2015-5-16 23:34 编辑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>
#pragmacomment(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<<" ";
}
std::cout<<endl;
return true;
}
int main(void)
{
for (int i = 1;i<10000;i++)
{
div(i);
}
return 0;
} iszhishu 是个判断是否质数的函数 没带上 本帖最后由 jerryxjr1220 于 2016-10-12 15:53 编辑
迷雾少年 发表于 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.num == hnumlist.num -1 and hnumlist.num == hnumlist.num -1 and hnumlist.num == hnumlist.num -1:
if len(hnumlist.yue) == 4 and len(hnumlist.yue) == 4 and len(hnumlist.yue) == 4 and len(hnumlist.yue) == 4:
print(hnumlist.num, hnumlist.yue)
break
# encoding:utf-8
# 找出最小的不能写作一个质数与一个平方数的二倍之和的奇合数
from time import time
from math import sqrt
def getPrimes(N):
primes = * N
primes, primes = False, False
for i, prime in enumerate(primes):
if prime:
for j in range(i * i, N, i):
primes = False
return
def findPrimeFactors(n, l_pr, s_pr):
if n in s_pr:
return
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 = 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: , 134044: , 134045: , 134046: }
cost 0.955096 sec
本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:20 编辑
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 = ;
n = n/PossiFactor(kk);
break
end
end
end
PrimeFactor = ;
Output = length(unique(PrimeFactor));
end
用的matlab：
结果是：
134043
时间已过 4.581318 秒。
>> #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;
}
}
} 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
本帖最后由 王小召 于 2019-6-24 14:31 编辑
借用楼上答案， 本题重点：对于大数据查找效率考量，速度从快到慢：set > dict > list 如果本题第16行用 if num in b_nums（也就是：in + list模式） 做替换，用时可能会多百倍，复杂度会从O(log N) 编程了 O(N)！!
结果是：{134043: , 134044: , 134045: , 134046: }
用时：0.6084039 秒
import time
def prime(N):
bool_num = * N
bool_num, bool_num = 0, 0
for i, j in enumerate(bool_num):
if j:
for x in range(i**2, N, i):
bool_num = 0
return
def composite_numbers(num, b_nums, s_nums, result = []):
if num in s_nums:
result.append(num)
return
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 = 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-8-5 13:44 编辑
王小召 发表于 2019-6-24 14:28
借用楼上答案， 本题重点：对于大数据查找效率考量，速度从快到慢：set > dict > list 如果本题第16行用 if ...
老哥说实话我看不懂你的代码…… 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;
int factor;
void euler_sieve(){
prime = false;
for (int i = 2;i <= M;i++) prime = true;
for (int i = 2;i <= M;i++){
if (prime) factor[++cnt] = i;
for (int j = 1;j <= cnt && i*factor < M;j++){
prime] = false;
if (i % factor == 0) break;
}
}
}
void solve(int x,set<int> & s){
for (int i = 1;x != 1;i++){
while (x % factor == 0){
s.insert(factor);
x /= factor;
}
}
}
bool judge(set<int> s[]){
for (int i = 0;i < 4;i++)
if (s.size() != 4) return false;
for (int i = 0;i < 3;i++){
for (int j = i+1;j < 4;j++){
if (s == s) return false;
}
}
return true;
}
int main(){
euler_sieve();
for (int i = 2;;i++){
set<int> s;
if (prime || prime || prime || prime) continue;
for (int j = 0;j < 4;j++) solve(i+j,s);
if (judge(s)) {cout << i << endl; break;}
}
return 0;
}
#找到一个数的所有质因数，运用元组
#找满足要求的下一个数
#两个列表，一个装质因数，一个装整数，用长度判断
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
是有点菜，但是幸好可以算出来 迷雾少年 发表于 2016-8-30 21:56
怎么我出来了好多。。
16:2 2 2 2
24:2 2 2 3
你再看看题目 #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 于 2022-1-8 12:35 编辑
/*
欧拉问题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;
int k = 647;
int nResult = INF;
p = 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 = '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;
}
页:
[1]