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

Stubborn

阴阳神万物主 发表于 2019-12-24 13:30
岂止提速一半，看这架势速度比之前几乎快了四倍啊

只减少了一半的空间量啊，不为偶数分配内存空间

findland

1. import math as m
   
2. def is_prime(num):
   
3.     if num<2:
   
4.         return False
   
5.     elif num==2:
   
6.         return True
   
7.     elif num%2==0:
   
8.         return False
   
9.     else:
   
10.             
    
11.         for i in range(3,int(m.sqrt(num)+1),2):
    
12.             if num%i==0:
    
13.                 return False
    
14.         else:
    
15.             return True
    
16. 
    
17. def prime(num):
    
18.     for i in range(2,num):
    
19.         if is_prime(i):
    
20.             yield i
    
21.             
    
22. def f293(m):
    
23.     count=0
    
24.     for i in prime(m):
    
25.         count+=1
    
26.     return count
    
27. 
    

复制代码

colinshi

代码写的太多懒得上代码了，给点我的思路吧
质数的的特点，只能被自己或者1整除。
任何自然数可以表示层6N 6N+1 6N+2 6N+3 6N+4 6N+5
其中6N 6N+2 6N+3 6N+4必然不是质数
剩余6N+1和6N+5可能存在质数。
同事6N+5也可以写成6N-1
那么我们可以剔除所有不能写成6N±1的数。
一个数如果不能被小于他的质数整除那么这个数就是质数。
一个数（N）不能被小于根号N的数整除，那么这个数就是质数。
归根到底还是数学题

zltzlt

凌九霄 发表于 2019-12-23 20:53

解答错误

输入：2
输出：1
预期结果：0

zltzlt

阴阳神万物主 发表于 2019-12-23 21:12
抢地板。
我尽力了，暂时想不到怎样能更高效了。
大写的监介，刚刚忘记验证结果了……

解答错误

输入：4
输出：3
预期结果：2

闲愚

1. import time
   
2. 
   
3. def func_293(n):
   
4.     count = 0
   
5.     num = 2
   
6.     while num < n:
   
7.         for i in range(2,num):
   
8.             if num % i == 0:
   
9.                 break
   
10.             else:
    
11.                 pass
    
12.         else:
    
13.             count += 1
    
14.         num += 1
    
15.     return count
    
16. 
    
17. a = time.perf_counter()
    
18. print(func_293(78498))
    
19. b = time.perf_counter()
    
20. print(b - a)
    
21. 
    
22. 
    
23. 7702
    
24. 用时 23.8712093

复制代码

零0℃度

1. class Solution:
   
2.     def countPrimes(self, n):
   
3.         if n <= 2:
   
4.             return 0
   
5.         res = [True] * n
   
6.         res[0] = res[1] = False
   
7.         for i in range(2, n):
   
8.             if res[i] is True:
   
9.                 for j in range(2, (n - 1) // i + 1):
   
10.                     res[i * j] = False
    
11.         return sum(res)

复制代码

阴阳神万物主

zltzlt 发表于 2019-12-24 20:53
解答错误

输入：4

不会吧？！

                               
登录/注册后可看大图

能有那个故障？

1. log = []
   
2. def solve(n:'int 非负整数'):
   
3.     if log:
   
4.         primes = [x for x in log if x<n]
   
5.         #print('调试',primes,n)
   
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)

复制代码

我这里输入 4 结果是 2 啊

1. >>> solve(4)
   
2. 2
   
3. >>> solve(4)
   
4. 2
   
5. >>>

复制代码

阴阳神万物主

colinshi 发表于 2019-12-24 20:26
代码写的太多懒得上代码了，给点我的思路吧
质数的的特点，只能被自己或者1整除。
任何自然数可以表示层6 ...

反驳：当 N 取值为 0 时 ， 6N+2 = 2 ，6N+3 = 3 ，都是质数。
你描述的语言中 “必然” 用得不对，如果说用对了，那么就是这个说法有问题，起码当 N=0 时，不成立。

fan1993423

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

这到底是个什么思路

Stubborn

fan1993423 发表于 2019-12-25 10:37
这到底是个什么思路

上面还是下面的那个？

fan1993423

Stubborn 发表于 2019-12-25 14:29
上面还是下面的那个？

下面那个

18463102026

1. import math
   
2. def fun1(n):
   
3.     if n<=2:
   
4.         return 0
   
5.     elif n==3:
   
6.         return 1
   
7.     elif 3 < n <=5:
   
8.         return 2
   
9.     count = 2
   
10.     for i in range(5,n,6):
    
11.         for j in range(3, int(math.sqrt(i) + 1), 2):
    
12.             if i % j == 0:
    
13.                 break
    
14.         else :
    
15.             count += 1
    
16.     for i in range(7,n,6):
    
17.         for j in range(3, int(math.sqrt(i) + 1), 2):
    
18.             if i % j == 0:
    
19.                 break
    
20.         else :
    
21.             count += 1
    
22.     return count

复制代码

Stubborn

fan1993423 发表于 2019-12-25 17:28
下面那个

上面那个懂的话，下面那个说白了就是不给偶数分配内存空间，这样可以减少一半的空间量

zltzlt

阴阳神万物主 发表于 2019-12-24 23:48
不会吧？！能有那个故障？

我这里输入 4 结果是 2 啊

是多次调用函数后全局变量 log 惹的祸。

zltzlt

newbison 发表于 2019-12-24 09:24

解答错误

输入：0
输出：False
预期结果：0

zltzlt

沙里爬 发表于 2019-12-24 10:18

输入大数据超时

zltzlt

LJZheng 发表于 2019-12-24 13:53

解答错误

输入：2
输出：1
预期结果：0

fan1993423

Stubborn 发表于 2019-12-25 18:36
上面那个懂的话，下面那个说白了就是不给偶数分配内存空间，这样可以减少一半的空间量

好吧。上面那个return写的好复杂，还不如return primes.count(True)来的简单

Stubborn

fan1993423 发表于 2019-12-25 22:46
好吧。上面那个return写的好复杂，还不如return primes.count(True)来的简单

上面的在找为True的索引，没有记录个数