质数

质数判定

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

n=int(input())
for i in range(n):
    a=int(input())
    if is_prime(a):
        print('Yes')
    else:
        print('No')

分解质因数

def divide(n):
    i=2
    while i<=n//i: 
        if n%i==0:
            s=0
            while n%i==0:
                n//=i   #将该数整除
                s+=1    #更新质数
            print(i,s)
        i+=1
    if n>1:
        print(n,1)

m=int(input())
while m:
    m-=1
    n=int(input())
    divide(n)
    print()

筛质数(线性筛法)

N=1000010
zhi=[0]*N
st=[False]*N
idx=0
def prime(n):
    global idx
    for i in range(2,n+1):
        if not st[i]:
            zhi[idx]=i
            idx+=1
            j=i*2
            while j<=n:
                st[j]=True
                j+=i
n=int(input())
prime(n)

约数

求约数

def devide(n):
    i=1
    li=[]
    while i<=n//i:
        if n%i==0:
            li.append(i)
            if i!=n//i:
                li.append(n//i)
        i+=1
    li.sort()
    return li

n=int(input())
for i in range(n):
    a=int(input())
    li=devide(a)
    for i in li:
        print(i,end=' ')
    print()

约数个数

mod=1e9+7
primes={}
n=int(input())
for i in range(n):
    a=int(input())
    i=2
    while i<=a//i:
        while a%i==0:
            a//=i
            if i in primes:
                primes[i]+=1
            else:
                primes[i]=1
        i+=1
    if a>1:
        if a in primes:
            primes[a]+=1
        else:
            primes[a]=1

res=1
for i in primes.values():
    res=int(res*(i+1)%mod)
print(res)

约数之和

mod=int(1e9+7)
primes={}
n=int(input())
for i in range(n):
    a=int(input())
    i=2
    while i<=a//i:
        while a%i==0:
            a//=i
            if i in primes:
                primes[i]+=1
            else:
                primes[i]=1
        i+=1
    if a>1:
        if a in primes:
            primes[a]+=1
        else:
            primes[a]=1

res=1
for i,val in primes.items():
    t=1
    while val:
        val-=1
        t=(t*i+1)%mod
    res=res*t%mod
print(res)

最大公约数

def gcd(a,b):
    if b!=0:
        return gcd(b,a%b)
    else:
        return a
n = int(input())
while n:
    n-=1
    a,b = map(int,input().split())
    print(gcd(a,b))

快速幂

快速幂可使用pow函数，pow(a,b,mod),底数为a，指数为b，mod为取模

n=int(input())
while n:
    n-=1
    a,b,p=map(int,input().split())
    ans=pow(a,b,p)
    print(ans)

求组合数

N=2010
mod=int(1e9+7)
c=[[0]*N for i in range(N)]

def init():
    for i in range(N):
        for j in range(i+1):
            if not j:
                c[i][j]=1
            else:
                c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod     #有点像dp

init() 
n=int(input())
while n:
    n-=1
    a,b=map(int,input().split())
    print(c[a][b])

阶乘可直接使用factorial

from math import *
mod=int(1e9+7)
n=int(input())
for i in range(n):
    a,b=map(int,input().split())
    print((factorial(a)//(factorial(a-b)*factorial(b)))%mod)    #阶乘函数