使用Python查找给定数组中Distinct Prime的总数
使用Python查找给定数组中Distinct Prime的总数
提问于 2018-08-05 20:47:39
问题是这样的--你给出了一个有N个整数的数组A。假设G是A的所有元素的乘积，你必须找出G的不同素因数的个数。示例-输入:A= 1，2，3，4输出:2
说明:这里g= 1*2*3*4，g的不同素因子是2和3，不同素因子的总数=2
下面是我写的代码，但我得到的输出是错误的-
class prime:
# @param A : list of integers
# @return an integer
def prime(self,num):
if(num>1):
for i in range(2,num):
if(num%i==0):
break
else:
return num
def solve(self, A):
prod = 1
tot = 0
for i in range(0,len(A)):
prod = prod*A[i]
for i in range(0,len(A)):
if(self.prime(A[i])):
if(prod%self.prime(A[i])==0):
tot = tot+1
return tot
A = [1,2,3,4]
prime().solve(A))回答 3
Stack Overflow用户
回答已采纳
发布于 2018-08-09 02:33:03
在看完OP的给定输入和输出后，我理解了OP想要计算质数的数量，这可以完全除以prod (元素的乘积)，并将余数设为0。OP -g= 1*2* 3 *4的输入1和g的不同素因子是2和3。OP -g= 96*98*5* 41 *80的输入2的不同素因子总数是2,3,5,7和41。不同素因子的总数=5
上面问题的代码-
class Solution:
# @param A : list of integers
# @return an integer
def prime(self,num):
if(num==1):
return 0
for i in range(2,(num//2+1)):
if(num%i==0):
return 0
return num
def solve(self, A):
prod = 1
tot = 0
for i in range(0,len(A)):
prod = prod*A[i]
for i in range(1,(prod//2+1)):
pr = self.prime(i)
if(pr):
#77145600
print("Prime :",pr)
if(prod%pr==0):
tot = tot+1
return tot
A = [96,98,5,41,80]
print(Solution().solve(A))但是对于这段代码，响应时间非常长。对于此输入- 96,98,5,41,80，响应时间超过5小时。有人能为它提供更好的解决方案吗？
我找到了一个比我上面提到的更好的解决方案-
更新了新代码-
# Python Program to find the prime number
def prime(num):
if(num==1):
return 0
for i in range(2,(num//2+1)):
if(num%i==0):
return 0
return num
# Python Program to find the factors of a number
def findFactors(x):
# This function takes a number and finds the factors
total = 0
for i in range(1, x + 1):
if x % i == 0:
if(prime(i)!=0):
print("Prime : ",prime(i))
total+=1
print("Total : ",total)
return total
# change this value for a different result.
num = 77145600
findFactors(num)findFactors函数首先找到给定数目的因子，然后使用素数函数检查找到的因子是否是素数。如果它是一个质数，那么我会将总数加1。在我的系统上，执行时间是45秒。
Stack Overflow用户
发布于 2018-08-05 21:04:27
class prime:
# @param A : list of integers
# @return an integer
def prime(self,num):
if num == 2: # changes
return num # changes
if(num>2): # changes
for i in range(2,num):
if(num%i==0):
break
else:
return num
def solve(self, A):
prod = 1
tot = 0
for i in range(0,len(A)):
prod = prod*A[i]
for i in range(0,len(A)):
if(self.prime(A[i])):
if(prod%self.prime(A[i])==0):
tot = tot+1
return tot
A = [1,2,3,4]
print(prime().solve(A))已更改的行用# changes注释
Stack Overflow用户
发布于 2018-08-06 02:51:16
from math import sqrt
from itertools import count, islice
class Prime:
def prime(self, n):
if n < 2:
return False
for number in islice(count(2), int(sqrt(n) - 1)):
if n % number == 0:
return False
return True
def solve(self, A):
prod = 1
tot = 0
for i in range(0, len(A)):
prod = prod * A[i]
if(prod<2):
return 0
if(prod == 2 or prod == 3):
return 1
for i in range(2, prod/2+1):
if(self.prime(i) and prod % i ==0):
tot =tot+1
return tot
A = [1,2,3,4]
print(Prime().solve(A))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51694459
复制相关文章
相似问题