使用Python查找给定数组中Distinct Prime的总数 [英] Find total count of Distinct Prime in given array using Python

问题描述

问题是这样的-您给定了一个具有N个整数的数组A.假设G是A的所有元素的乘积.您必须找到G的不同素数的数量.例子 -输入 :A = 1、2、3、4输出 :2

The problem is like this - You have given an array A having N integers. Let say G is the product of all elements of A. You have to find the number of distinct prime divisors of G. Example - Input : A = 1, 2, 3, 4 Output : 2

说明:在这里g = 1 * 2 * 3 * 4g的不同素数除数是2和3总共不同的素数除数= 2

Explanation : Here g = 1*2*3*4 and distinct prime divisor of g are 2 and 3 To total count of distinct prime divisor = 2

下面是我写的代码，但是我得到的输出是错误的-

Below is the code i wrote but the output which i am getting is wrong -

  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))

推荐答案

在经过OP的给定输入和输出之后，我了解到OP希望计算可以完全除掉prod(元素乘积)的素数.并将余数设为0.OP的输入1-g = 1 * 2 * 3 * 4，且g的唯一质数为2和3.OP的输入2-g = 96 * 98 * 5 * 41 * 80，g的不同素数为2、3、5、7和41.不同素数的总数为5

After going through the give inputs and outputs by the OP i understood that OP wants to count the number of primes which can completely divide the prod (product of element) and give remainder as 0. Input 1 by OP - g = 1*2*3*4 and distinct prime divisor of g are 2 and 3. Total count of distinct prime divisor = 2 Input 2 by OP - g = 96*98*5*41*80 and distinct prime divisor of g are 2,3,5,7 and 41. Total count of distinct prime divisor = 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小时.谁能为此提供更好的解决方案?

But for this code, the response time is very high. For this input - 96,98,5,41,80 the response time was more than 5 hours. Can anyone provide a better solution for it?

我找到了一个比我上面提到的更好的解决方案-

I found a better solution then the above mentioned by me -

更新后的新代码-

# 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秒.

The findFactors function first finds the factors of given number and then by using prime function I am checking whether the found factor is prime or not. If it is a prime number then I am incrementing the total by 1. Execution time is 45 seconds on my system.

这篇关于使用Python查找给定数组中Distinct Prime的总数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！