python求约数的个数

题⽬：输⼊n个整数,依次输出每个数的约数的个数（运⾏时间1500ms）

import osdef count(x): factor = 2 num = 1

while (factor * factor <= x): count = 1

while (x % factor == 0): count += 1 x /= factor num *= count factor += 1

return (num * (1 + (x > 1)))try:

n = int(input()) # ⾏数 if(n!=0):

#if(n>0 and n<=1000):

s = list(map(int, input().split())) #print(s) else:

os._exit(0) for item in s: it=count(item) print(it)except: pass

View Code

python计算约数个数的⽅法：转⾃：

从1到n枚举，判断是否可以整除 时间复杂度O（n)

def countDivisors(num):

return sum(num % i == 0 for i in range(1, num + 1))

从1到sqrt（n）枚举，判断是否可以整除

def countDivisors(num): cnt = 0

sqrt = int(num ** 0.5)

for x in range(1, sqrt + 1): if num % x == 0: cnt += 1

return cnt * 2 - (sqrt ** 2 == num)

分解质因⼦，求幂的乘积

def countDivisors(num): ans = 1 x = 2

while x * x <= num: cnt = 1

while num % x == 0: cnt += 1 num /= x ans *= cnt x += 1

return ans * (1 + (num > 1))

李旭的java代码（运⾏时间200ms）为什么这个这么快呢

public class yue {

public static void main(String[] args) { System.out.println(\"N:\");

Scanner sc = new Scanner(System.in); int n =sc.nextInt(); int []a=new int[n]; for (int i=0;ifor(int i=0;ifor(int j=1;j*j<=a[i];j++){ if(j*j==a[i]) { num++;

}else if(a[i]%j==0){ num+=2; } }

System.out.println(num); }

}}

View Code