MillerRabin算法

算法描述

• 该算法为随机化算法，适用于大数的素性测试，时间复杂度为O(T*logn)
• 若不通过测试则该数一定为合数
• 若通过测试则该数不为素数的概率小于1/4
• 进行t次检验若均通过则该数为素数的概率为 1-4^(-t)

算法流程

1. 输入正整数x, x>=3
2. 计算奇数q和整数k，满足q*2^k=x-1
3. 任选整数a属于(1,x-1)
4. 若a^q mod x=1则通过测试
5. 若a^(q*2^i) mod x=x-1则通过测试，i属于[0,k)，有一次通过即可
6. 若上述均不满足则不通过测试

代码实现

#include <stdlib.h> 
#include <stdio.h>
#define ull unsigned long long

ull pow(ull x, ull y, ull z) {
    ull res = 1;
    for(; y; y >>= 1) {
        if(y & 1) res = (res % z * x % z) % z;
        x = (x % z * x % z) % z;
    }
    return res;
}

int MillerRabin(ull x) {
    ull q = x - 1, k = 0;
    while(!(q & 1)) {
        q >>= 1;
        k++;
    }
    ull a = rand() % (x - 2) + 2; 
    if(pow(a, q, x) == 1) return 1;
    for(int i = 0; i < k; i++) {
        if(pow(a, q, x) == x - 1) return 1; 
        q <<= 1;
    }
    return 0;
}

int test(ull x) {
	if(x == 2) return 1;
    for(int i = 1; i <= 10; i++) {
        if(!MillerRabin(x)) return 0;
    }
    return 1;
}

int main()
{
	printf("2\n");
    for(int i = 3; i < 1e5; i += 2) {
    	if(test(i)) printf("%d\n", i);
	}
    return 0;
}

$欧拉筛$$（Python）$$虽然比C慢，但是稍微大于60ms在Py里面也算快的了吧👀️$

status=[False]*2+[True]*(100000-1)
primes=[2]
print(2)
for i in range(3,100000+1,2):
    if status[i]:
        primes.append(i)
        print(i)
    if i<=100000//2:
        for j in primes:
            if i*j>100000:
                break
            elif i%j==0:
                status[i * j] = False
                break
            else:
                status[i*j]=False

for i in range(2,100000):
    t=1
    b=int(i**0.5)
    for k in range(2,b+1):
        if i%k==0:
            t=0
            break
    while t==1:
         print(i)
         break

这个就是程序啦

就是递推的意思（差不多吧） 反正就是一个思想： 如果有一个新数，那它只会有两种可能 1，它可以被已知比它小的质数整除 2，它本身就是一个新的质数

a=[2,3]
for i in range(4,100001):  #100001可以改小一点用于测试代码
    flag=True
    for j in range(len(a)):
        if i%a[j]==0:
            flag=False
            break
        if a[j]>i**0.5:
            break
    if flag==True:
        a.append(i)
for i in a:
    print(i)

#include <iostream>

using namespace std; long long a[100005]; int main() { int cnt=1; a[1]=2; for(int i=3;i<=100000;i++) { int t=1; for(int j=1;j<=cnt;j++) { if(i%a[j]==0) {t=0; break;

}
    }
    if(t==1)
    {
        cnt++;
        a[cnt]=i;
    }
}
for(int i=1;i<=cnt;i++)
{
    cout<<a[i]<<endl;
}
return 0;

}

#include <iostream> #include <cmath> using namespace std; bool prim(int m); int main() { printf("2\n"); for(int i=3;i<=100000000;i+=2){ if(prim(i)){ printf("%d\n",i); } }return 0; }

bool prim(int m){ bool flag=true; int k=sqrt(m); for(int i=2;i<=k;i++){ if(m%i==0){ flag=false; break; } } return flag; }

for i in range(2,100): for k in range(2,i): if i%k==0: break else: print(i) #旧oj题解