献芹奏曝-Python面试题-算法-数学篇

标签：prime index 面试题 Python 质数 count 献芹 int str

上一篇：献芹奏曝-Python面试题 

      开篇的话：本文目的是收集和归纳力扣上的算法题，希望用python语言，竭我所能做到思路最清奇、代码最简洁、方法最广泛、性能最高效，了解常见题目，找到最利于记忆的答案，更加从容的应对面试。希望广思集益，共同进步。

一、质数

204. 计数质数（难度系数✯✯） 

class Solution:
    def countPrimes(self, n: int) -> int:
        # 何为质数：除了1和它本身外，不能被其他自然数（质数）整除
        count = 0
        if n<2:
            return count
        for i in range(2,n):
            j = 2
            while j<i:
                if i%j == 0:
                    break
                j += 1
            else:
                count += 1
        return count 

方法一：暴力破解

运行结果：1：超时 

知识点/技巧:1：何为质数：除了1和它本身外，不能被其他自然数（质数）整除

class Solution:
    def countPrimes(self, n: int) -> int:
        # 何为质数：除了1和它本身外，不能被其他自然数（质数）整除
        count = 0
        r_list = [True]*n
        for index in range(2,n):
            if r_list[index]:
                count += 1
                for i in range(index*index,n,index):
                    r_list[i] = False            
        return count 

埃氏筛选法

运行结果：1：耗时超过67%。2：内存超过58% 

知识点/技巧:1：埃氏筛选法

 HJ6 质数因子（难度系数✯✯） 

import sys
import math

for line in sys.stdin:
    a = int(line.strip())
    prime = 2
    an_str = ""
    while prime < int(math.sqrt(a))+1:
        if a%prime !=0:
            prime += 1
        else:
            a = a//prime
            an_str += str(prime)+' '
            prime = 2
    if a > 2:
        an_str += str(a)
    print(an_str)

View Code

知识点/技巧:1：先用开方缩小范围

 

标签：prime,index,面试题,Python,质数,count,献芹,int,str
From： https://www.cnblogs.com/YK2012/p/16951543.html