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

Stubborn

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

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

findland

import math as m
def is_prime(num):
    if num<2:
        return False
    elif num==2:
        return True
    elif num%2==0:
        return False
    else:
             
        for i in range(3,int(m.sqrt(num)+1),2):
            if num%i==0:
                return False
        else:
            return True

def prime(num):
    for i in range(2,num):
        if is_prime(i):
            yield i
            
def f293(m):
    count=0
    for i in prime(m):
        count+=1
    return count

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

闲愚

import time

def func_293(n):
    count = 0
    num = 2
    while num < n:
        for i in range(2,num):
            if num % i == 0:
                break
            else:
                pass
        else:
            count += 1
        num += 1
    return count

a = time.perf_counter()
print(func_293(78498))
b = time.perf_counter()
print(b - a)


7702
用时 23.8712093

零0℃度

class Solution:
    def countPrimes(self, n):
        if n <= 2:
            return 0
        res = [True] * n
        res[0] = res[1] = False
        for i in range(2, n):
            if res[i] is True:
                for j in range(2, (n - 1) // i + 1):
                    res[i * j] = False
        return sum(res)

阴阳神万物主

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

输入：4

不会吧？！

                               
登录/注册后可看大图

能有那个故障？

log = []
def solve(n:'int 非负整数'):
    if log:
        primes = [x for x in log if x<n]
        #print('调试',primes,n)
        res = primes[-1] if primes else 2
    else:
        primes = []
        res = 2
        if res < n:
            primes.append(res)
        res = 3
    for res in range(res,n,2):
        out = False
        for sub in primes:
            if sub**2 > res:
                break
            elif not res%sub:
                out = True
                break
        if out:
            continue
        else:
            primes.append(res)
            if res not in log:
                log.append(res)
    return len(primes)

我这里输入 4 结果是 2 啊

>>> solve(4)
2
>>> solve(4)
2
>>> 

阴阳神万物主

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

import math
def fun1(n):
    if n<=2:
        return 0
    elif n==3:
        return 1
    elif 3 < n <=5:
        return 2
    count = 2 
    for i in range(5,n,6):
        for j in range(3, int(math.sqrt(i) + 1), 2):
            if i % j == 0:
                break
        else :
            count += 1
    for i in range(7,n,6):
        for j in range(3, int(math.sqrt(i) + 1), 2):
            if i % j == 0:
                break
        else :
            count += 1
    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的索引，没有记录个数