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

zltzlt

今天的题目：

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

示例 1：

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

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Croper

2019-12-23 21:05:10

def func293(n):
    if (n<=2):
        return 0
    primes=[2]
    def isprime(num):
        for i in primes:
            if (i**2>num):
                return True
            if (num % i==0):
                return False
    i=3
    while (i<n):
        if isprime(i):
            primes.append(i)
        i+=2

    return len(primes)

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

def func293(n):
    if (n<=2):
        return 0;
    s=[True]*n
    s[0]=False
    s[1]=False
    for i in range(2,n):
        if i**2>n:
            break
        if not s[i]:
            continue
        for j in range(i*2,n,i):
            s[j]=False
    return sum(s)

跳转到最佳答案楼层

凌九霄

import math


def count_prime(number):
    if number < 2: return 0
    K = 1
    for i in range(3, number):
        M = 1
        if i % 2 == 0:
            M = 0
            continue
        for j in range(3, int(math.sqrt(i) + 1), 2):
            if i % j == 0:
                M = 0
                break
        if M == 1:
            K += 1
    return K

Croper

def func293(n):
    if (n<=2):
        return 0
    primes=[2]
    def isprime(num):
        for i in primes:
            if (i**2>num):
                return True
            if (num % i==0):
                return False
    i=3
    while (i<n):
        if isprime(i):
            primes.append(i)
        i+=2

    return len(primes)

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

def func293(n):
    if (n<=2):
        return 0;
    s=[True]*n
    s[0]=False
    s[1]=False
    for i in range(2,n):
        if i**2>n:
            break
        if not s[i]:
            continue
        for j in range(i*2,n,i):
            s[j]=False
    return sum(s)

zltzlt

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

是，看效率。

阴阳神万物主

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

                               
登录/注册后可看大图

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

                               
登录/注册后可看大图

代码：

log = []
def solve(n:'int 非负整数'):
    if log:
        primes = [x for x in log if x<n]
        #print('调试',primes)
        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)
if __name__ == '__main__':
    print('示例1 输出：',solve(10))

我自行测试的结果：

>>> import time
>>> for n in range(20):
        num = 10**n
        a = time.perf_counter()
        get = solve(num)
        b = time.perf_counter()
        print(get,'用时',b-a,'s',n)

        
0 用时 9.300000000322939e-06 s 0
4 用时 1.6600000000366322e-05 s 1
25 用时 0.00010729999999981032 s 2
168 用时 0.0009782000000004842 s 3
1229 用时 0.02421449999999936 s 4
9592 用时 0.9459274999999998 s 5
78498 用时 52.4094105 s 6

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

冬雪雪冬

def fun(num):
    if num <= 2:
        return 0
    prime = [2]
    for i in range(3, num, 2):
        for j in prime:
            if i % j == 0:
                break
        else:
            prime.append(i)
    return len(prime)

fan1993423

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

hrp

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

TJBEST

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

def fun293(n):
    if 0 <= n <=2:
        return 0
    else:
        selectlist = [2]
        for eachNum in range(3,n):
            status = 1
            for eachSu in selectlist:
                if eachNum % eachSu ==0:
                    status = 0
                    break
            if status == 1:
                selectlist.append(eachNum)
        return len(selectlist)

danteer

那我也抢个位置吧

def solve(n):
    def generator():
        list1 = [2]
        number = 3
        while True:
            yield list1[-1]
            flag = True
            while flag:
                flag = False
                for each in list1:
                    if ((2*each) > number):
                        break
                    if (number % each == 0):
                        number += 2
                        flag = True
                        break
            list1.append(number)
            number += 2
    x = generator()
    result = 0
    while next(x) < n:
        result += 1
    return result

Stubborn

def fun293(n):
    if n == 1: return 0
    primes = [True] * n
    primes[0], primes[1] = False, False
    for (i, prime) in enumerate(primes):
        if prime:
            for j in range(i * i, n, i): primes[j] = False
    return len([k for (k, trueprime) in enumerate(primes) if trueprime])

import time
for n in range(10):
        num = 10**n
        a = time.perf_counter()
        get = fun293(num)
        b = time.perf_counter()
        print(get,'用时',b-a,'s',n)

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

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

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

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

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

Unicorn#

估计不行

def solve(num):
    primes = []
    for i in range(2, num):
        isprime = True
        for prime in primes:
            if i % prime == 0:
                isprime = False
                break
        if isprime:
            primes.append(i)
    return len(primes)

阴阳神万物主

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

嗯，会超出内存限制

Stubborn

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

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

Seawolf

def func(n):
        if n < 2:
            return 0
        s = [1] * n
        s[0] = s[1] = 0
        for i in range(2, int(n ** 0.5) + 1):
            if s[i] == 1:
                s[i * i:n:i] = [0] * len(s[i * i:n:i])
        return sum(s)

fan1993423

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

newbison

#输出一个数有多少素数
#输入 10--> 输出4，小于10的素数有2，3，5，7，总共4个素数，所以答案是4。

import math

def is_prime(n):  #第一个程序，判断是否为素数
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def solution(n): # 查找小于n的整数有多少个素数
    if n <= 10 and n >= 2:
        res = [i for i in range(2, n+1) if is_prime(i)] 
    elif n <2:
        return False 
    else:
        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]
    #对于大于10的数，为了减少运算次数，去除2，3，5，7。。。的倍数。
        for each in res:
            if not is_prime(each):
                res.remove(each)
    return len(res)

沙里爬

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

def solution(n):
    a=0
    if n <= 2:
        print(0)
    elif n == 3:
        print(1)
    else:
        for i in range(2,n):
            if is_prime(i):
                a += 1
        print(a)

阴阳神万物主

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

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

LJZheng

def p293(n):
    if n > 2:
        l = [2]
        for i in range(3, n):
            for j in l:
                if i % j == 0:
                    break
            else:
                l.append(i)
        return len(l)
    elif n == 2:
        return 1
    else:
        return 0