【每日一题0730】寻找质数

兴趣爱好交流 每日一题
1

:woman_mage:给你一个整数n，且n>=3，请编写一个python函数，返回n（不含自己）以内所有的质数。

题目难度：中等
题目来源：shoppe面试真题

def find_prime(n) -> list:
    pass
    
assert find_prime(10) == [2,3,5,7]
assert find_prime(17) == [2,3,5, 7,11,13]
2

双循环，不过时间复杂度有点高， 求优化 :joy:

def solution(n):
    res=[2]
    for i in range(3,n,2):
        num=0
        for j in range(2,i):
            if i%j==0:
                num=num+1
        if num==0:
            res.append(i)
    return res
3

还是双循环，比你快了一点点

def find_prime(n) -> list:
    rt = []
    for i in range(1, n):
        for j in range(2, i):
            if (i % j) == 0:
                break
        else:
            rt.append(i)
    return rt
2 个赞
4 
    public List<Integer> findPrime(int n) {
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 2; i < n; i++) {
            boolean isFlag = true;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    isFlag = false;
                    break;
                }
            }
            if (isFlag) {
                res.add(i);
            }
        }
        return res;
    }
5

也是双循环，比你的短了一点点

def find_prime(n):
    return [x for x in range(2,n) if not [y for y in range(2,x) if x % y == 0]]

assert find_prime(10) == [2,3,5,7]
assert find_prime(17) == [2,3,5, 7,11,13]

:partying_face: :partying_face: :partying_face: :partying_face: :partying_face: :partying_face:

1 个赞
7

image

8 
def find_prime(n) -> list:
    result = []
    for x in range(2, n):
        for y in range(2, x):
            if x % y == 0:
                break
        else:
            result.append(x)
    return result


assert find_prime(10) == [2, 3, 5, 7]
assert find_prime(17) == [2, 3, 5, 7, 11, 13]
1 个赞
9 
    def find_prime(n:int) -> list:
        if n < 3:return None
        prime_list = [2]
        for i in range(3,n):
            status = 1
            for j in prime_list:
                if i % j == 0:
                    status = 0
                    break
            if status == 0:continue
            prime_list.append(i)
        return prime_list
10 
def find_prime(n) -> list:
    list_1=[]
    for i in range(2, n):
        for y in range(2, i):
            if i%y==0:
                break
        else:
            list_1.append(i)
    return list_1
11 
def find_prime(n) -> list:
    li = [i for i in range(1,n) if [j for j in range(1,i+1) if i%j==0]==[1,i]]
    return li


assert find_prime(10) == [2, 3, 5, 7]
assert find_prime(17) == [2, 3, 5, 7, 11, 13]
12 
def find_prime(n) -> list:
    if n < 3:
        return "input is not valid"
    else:
        result=[2]
        for i in range(3,n,2):
            for j in range(2,i):
                if i%j==0:
                    break
            else:
                result.append(i)
        return result
13 
def find_prime(n) -> list:
    res_list = []
    for i in range(2, n):
        num = 0
        for j in range(2, i):
            if i % j == 0:
                num += 1
        if num == 0:
            res_list.append(i)
        else:
            continue
    return res_list


assert find_prime(10) == [2, 3, 5, 7]
assert find_prime(17) == [2, 3, 5, 7, 11, 13]