[已解决]Python：每日一题 293

zltzlt

今天的题目：

给定一个非负整数 n，返回所有小于 n 的质数的数量。

示例 1：

输入：10
输出：4
解释：小于 10 的质数一共有 4 个，它们是 2、3、5、7。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Croper

2019-12-23 21:05:10

1. def func293(n):
   
2.     if (n<=2):
   
3.         return 0
   
4.     primes=[2]
   
5.     def isprime(num):
   
6.         for i in primes:
   
7.             if (i**2>num):
   
8.                 return True
   
9.             if (num % i==0):
   
10.                 return False
    
11.     i=3
    
12.     while (i<n):
    
13.         if isprime(i):
    
14.             primes.append(i)
    
15.         i+=2
    
16. 
    
17.     return len(primes)

复制代码

...才想起这题leetcode上做过，当时用的C++写的，改成python的吧：

1. def func293(n):
   
2.     if (n<=2):
   
3.         return 0;
   
4.     s=[True]*n
   
5.     s[0]=False
   
6.     s[1]=False
   
7.     for i in range(2,n):
   
8.         if i**2>n:
   
9.             break
   
10.         if not s[i]:
    
11.             continue
    
12.         for j in range(i*2,n,i):
    
13.             s[j]=False
    
14.     return sum(s)

复制代码

跳转到最佳答案楼层

凌九霄

1. import math
   
2. 
   
3. 
   
4. def count_prime(number):
   
5.     if number < 2: return 0
   
6.     K = 1
   
7.     for i in range(3, number):
   
8.         M = 1
   
9.         if i % 2 == 0:
   
10.             M = 0
    
11.             continue
    
12.         for j in range(3, int(math.sqrt(i) + 1), 2):
    
13.             if i % j == 0:
    
14.                 M = 0
    
15.                 break
    
16.         if M == 1:
    
17.             K += 1
    
18.     return K

复制代码

Croper

1. def func293(n):
   
2.     if (n<=2):
   
3.         return 0
   
4.     primes=[2]
   
5.     def isprime(num):
   
6.         for i in primes:
   
7.             if (i**2>num):
   
8.                 return True
   
9.             if (num % i==0):
   
10.                 return False
    
11.     i=3
    
12.     while (i<n):
    
13.         if isprime(i):
    
14.             primes.append(i)
    
15.         i+=2
    
16. 
    
17.     return len(primes)

复制代码

...才想起这题leetcode上做过，当时用的C++写的，改成python的吧：

1. def func293(n):
   
2.     if (n<=2):
   
3.         return 0;
   
4.     s=[True]*n
   
5.     s[0]=False
   
6.     s[1]=False
   
7.     for i in range(2,n):
   
8.         if i**2>n:
   
9.             break
   
10.         if not s[i]:
    
11.             continue
    
12.         for j in range(i*2,n,i):
    
13.             s[j]=False
    
14.     return sum(s)

复制代码

zltzlt

凌九霄 发表于 2019-12-23 20:53
占个位置先，又是效率题吧

是，看效率。

阴阳神万物主

抢地板。
我尽力了，暂时想不到怎样能更高效了。

                               
登录/注册后可看大图

大写的监介，刚刚忘记验证结果了……

                               
登录/注册后可看大图

代码：

1. log = []
   
2. def solve(n:'int 非负整数'):
   
3.     if log:
   
4.         primes = [x for x in log if x<n]
   
5.         #print('调试',primes)
   
6.         res = primes[-1] if primes else 2
   
7.     else:
   
8.         primes = []
   
9.         res = 2
   
10.         if res < n:
    
11.             primes.append(res)
    
12.         res = 3
    
13.     for res in range(res,n,2):
    
14.         out = False
    
15.         for sub in primes:
    
16.             if sub**2 > res:
    
17.                 break
    
18.             elif not res%sub:
    
19.                 out = True
    
20.                 break
    
21.         if out:
    
22.             continue
    
23.         else:
    
24.             primes.append(res)
    
25.             if res not in log:
    
26.                 log.append(res)
    
27.     return len(primes)
    
28. if __name__ == '__main__':
    
29.     print('示例1 输出：',solve(10))
    
30. 
    

复制代码

我自行测试的结果：

1. >>> import time
   
2. >>> for n in range(20):
   
3.         num = 10**n
   
4.         a = time.perf_counter()
   
5.         get = solve(num)
   
6.         b = time.perf_counter()
   
7.         print(get,'用时',b-a,'s',n)
   
8. 
   
9.         
   
10. 0 用时 9.300000000322939e-06 s 0
    
11. 4 用时 1.6600000000366322e-05 s 1
    
12. 25 用时 0.00010729999999981032 s 2
    
13. 168 用时 0.0009782000000004842 s 3
    
14. 1229 用时 0.02421449999999936 s 4
    
15. 9592 用时 0.9459274999999998 s 5
    
16. 78498 用时 52.4094105 s 6
    

复制代码

时间复杂度的话，应该大约是 O(n^2)

冬雪雪冬

1. def fun(num):
   
2.     if num <= 2:
   
3.         return 0
   
4.     prime = [2]
   
5.     for i in range(3, num, 2):
   
6.         for j in prime:
   
7.             if i % j == 0:
   
8.                 break
   
9.         else:
   
10.             prime.append(i)
    
11.     return len(prime)

复制代码

fan1993423

1. def fun293(n):
   
2.     if n==1 or n==2:
   
3.         return f'小于{n}的质数不存在'
   
4.     k=[i for i in range(2,n) for j in range(2,i) if 0 in [i%j]]
   
5.     return f'小于{n}的质数数量有{n-2-len(set(k))}个'

复制代码

hrp

实在想不到高效算法，输入大数据都是超时

TJBEST

很惭愧 10000个数居然算了100毫秒 10万大概 8秒 真的太差劲了

1. def fun293(n):
   
2.     if 0 <= n <=2:
   
3.         return 0
   
4.     else:
   
5.         selectlist = [2]
   
6.         for eachNum in range(3,n):
   
7.             status = 1
   
8.             for eachSu in selectlist:
   
9.                 if eachNum % eachSu ==0:
   
10.                     status = 0
    
11.                     break
    
12.             if status == 1:
    
13.                 selectlist.append(eachNum)
    
14.         return len(selectlist)

复制代码

danteer

那我也抢个位置吧

1. def solve(n):
   
2.     def generator():
   
3.         list1 = [2]
   
4.         number = 3
   
5.         while True:
   
6.             yield list1[-1]
   
7.             flag = True
   
8.             while flag:
   
9.                 flag = False
   
10.                 for each in list1:
    
11.                     if ((2*each) > number):
    
12.                         break
    
13.                     if (number % each == 0):
    
14.                         number += 2
    
15.                         flag = True
    
16.                         break
    
17.             list1.append(number)
    
18.             number += 2
    
19.     x = generator()
    
20.     result = 0
    
21.     while next(x) < n:
    
22.         result += 1
    
23.     return result

复制代码

Stubborn

1. def fun293(n):
   
2.     if n == 1: return 0
   
3.     primes = [True] * n
   
4.     primes[0], primes[1] = False, False
   
5.     for (i, prime) in enumerate(primes):
   
6.         if prime:
   
7.             for j in range(i * i, n, i): primes[j] = False
   
8.     return len([k for (k, trueprime) in enumerate(primes) if trueprime])
   
9. 
   
10. import time
    
11. for n in range(10):
    
12.         num = 10**n
    
13.         a = time.perf_counter()
    
14.         get = fun293(num)
    
15.         b = time.perf_counter()
    
16.         print(get,'用时',b-a,'s',n)

复制代码

上了10**9就搞不定了，

1. 0 用时 1.0259999999595593e-06 s 0
   
2. 4 用时 1.2316000000012206e-05 s 1
   
3. 25 用时 3.746000000004468e-05 s 2
   
4. 168 用时 0.0003412480000000162 s 3
   
5. 1229 用时 0.00341709699999998 s 4
   
6. 9592 用时 0.037514688999999934 s 5
   
7. 78498 用时 0.376490329 s 6
   
8. 664579 用时 4.567675358 s 7
   
9. 5761455 用时 48.727864815 s 8

复制代码

想想还可以提速一半， 提速成功

1. def test(n: int):
   
2.     if n < 3: return 0
   
3.     count = 0
   
4.     primes = [True] * (n//2)
   
5.     for i in range(3, n, 2):
   
6.         if primes[i//2]:
   
7.             count += 1
   
8.             for j in range((i * i)//2, n//2, i): primes[j] = False
   
9.     return count + 1

复制代码

1. 0 用时 7.700000000006313e-07 s 0
   
2. 4 用时 5.7779999999979514e-06 s 1
   
3. 25 用时 1.2270999999997728e-05 s 2
   
4. 168 用时 0.00027523900000000004 s 3
   
5. 1229 用时 0.001398563999999998 s 4
   
6. 9592 用时 0.011049376999999999 s 5
   
7. 78498 用时 0.10091913899999999 s 6
   
8. 664579 用时 1.1721501019999998 s 7
   
9. 5761455 用时 12.463232227 s 8

复制代码

Unicorn#

估计不行

1. def solve(num):
   
2.     primes = []
   
3.     for i in range(2, num):
   
4.         isprime = True
   
5.         for prime in primes:
   
6.             if i % prime == 0:
   
7.                 isprime = False
   
8.                 break
   
9.         if isprime:
   
10.             primes.append(i)
    
11.     return len(primes)

复制代码

阴阳神万物主

Stubborn 发表于 2019-12-23 22:11
上了10**9就搞不定了，

嗯，会超出内存限制

Stubborn

阴阳神万物主 发表于 2019-12-24 01:30
嗯，会超出内存限制

没报错，但是慢，卡在哪里，估计是爆内存了 10亿的 list  估计内存吃紧

Seawolf

1. def func(n):
   
2.         if n < 2:
   
3.             return 0
   
4.         s = [1] * n
   
5.         s[0] = s[1] = 0
   
6.         for i in range(2, int(n ** 0.5) + 1):
   
7.             if s[i] == 1:
   
8.                 s[i * i:n:i] = [0] * len(s[i * i:n:i])
   
9.         return sum(s)

复制代码

fan1993423

我表示我的答案好像五位数就搞不定了，要着，看大佬们发挥了。

newbison

1. #输出一个数有多少素数
   
2. #输入 10--> 输出4，小于10的素数有2，3，5，7，总共4个素数，所以答案是4。
   
3. 
   
4. import math
   
5. 
   
6. def is_prime(n):  #第一个程序，判断是否为素数
   
7.     for i in range(2, int(math.sqrt(n))+1):
   
8.         if n % i == 0:
   
9.             return False
   
10.     return True
    
11. 
    
12. def solution(n): # 查找小于n的整数有多少个素数
    
13.     if n <= 10 and n >= 2:
    
14.         res = [i for i in range(2, n+1) if is_prime(i)]
    
15.     elif n <2:
    
16.         return False
    
17.     else:
    
18.         res = [2, 3, 5, 7] + [i for i in range(10, n+1) if i%2!=0 and i%3!=0 and i%5!=0 and i%7!=0]
    
19.     #对于大于10的数，为了减少运算次数，去除2，3，5，7。。。的倍数。
    
20.         for each in res:
    
21.             if not is_prime(each):
    
22.                 res.remove(each)
    
23.     return len(res)

复制代码

沙里爬

1. import math
   
2. def is_prime(num):
   
3.     for i in range(2,int(math.sqrt(num))+1):
   
4.         if num % i ==0:
   
5.             return False
   
6.     return True
   
7. 
   
8. def solution(n):
   
9.     a=0
   
10.     if n <= 2:
    
11.         print(0)
    
12.     elif n == 3:
    
13.         print(1)
    
14.     else:
    
15.         for i in range(2,n):
    
16.             if is_prime(i):
    
17.                 a += 1
    
18.         print(a)

复制代码

阴阳神万物主

Stubborn 发表于 2019-12-23 22:11
上了10**9就搞不定了，     

岂止提速一半，看这架势速度比之前几乎快了四倍啊

LJZheng

1. def p293(n):
   
2.     if n > 2:
   
3.         l = [2]
   
4.         for i in range(3, n):
   
5.             for j in l:
   
6.                 if i % j == 0:
   
7.                     break
   
8.             else:
   
9.                 l.append(i)
   
10.         return len(l)
    
11.     elif n == 2:
    
12.         return 1
    
13.     else:
    
14.         return 0

复制代码