使用 Python 在给定数组中查找不同素数的总数
Find total count of Distinct Prime in given array using Python
问题是这样的——
你给了一个有 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))
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
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))
在通过 OP 给出的输入和输出后,我了解到 OP 想要计算可以完全除掉 prod(元素的乘积)并将余数作为 0 的素数。
OP 的输入 1 - g = 1*2*3*4 并且 g 的不同素数除数为 2 和 3。不同素数除数的总数 = 2
OP 的输入 2 - g = 96*98*5*41*80 和 g 的不同质数除数是 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 函数首先找到给定数字的因子,然后通过使用 prime 函数检查找到的因子是否为素数。如果它是质数,那么我将总数增加 1。
在我的系统上执行时间是 45 秒。
问题是这样的—— 你给了一个有 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))
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
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))
在通过 OP 给出的输入和输出后,我了解到 OP 想要计算可以完全除掉 prod(元素的乘积)并将余数作为 0 的素数。 OP 的输入 1 - g = 1*2*3*4 并且 g 的不同素数除数为 2 和 3。不同素数除数的总数 = 2 OP 的输入 2 - g = 96*98*5*41*80 和 g 的不同质数除数是 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 函数首先找到给定数字的因子,然后通过使用 prime 函数检查找到的因子是否为素数。如果它是质数,那么我将总数增加 1。 在我的系统上执行时间是 45 秒。