poj 1014 多重背包
hdoj 1028 1398 母函数

Miller-Robbin 素数测试

scturtle posted @ 2010年7月02日 18:13 in algorithm , 3895 阅读

如果一个数是伪素数，他几乎肯定是素数，如果一个数不是伪素数，他一定不是素数。

不断读取2~n-1的基b(s次)，计算每次是否都有 exp(b,n-1)mod n == 1

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define maxn 100001
#define s 10
bool isprim[maxn];

void shai()
{
    for(int i=0;i<maxn;i++) isprim[i]=1;
    int t;
    for(int i=2;i<=maxn/2;i++)
    {
        t=i+i;
        while(t<maxn)
        {
            isprim[t]=0;
            t+=i;
        }
    }
}

int modexp(int a,int b,int m)
{
    __int64 ans=1;__int64 t=a%m;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*t)%m;
            b--;
        }
        t=(t*t)%m;
        b>>=1;
    }
    return ans;
}

bool MillerRobbin(int n)
{
    for(int i=1;i<=s;i++)
    {
        int a=rand()%(n-2)+2;
        if (modexp(a,n-1,n)!=1) return false;
    }
    return true;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    shai();
    for(int i=3;i<maxn;i++)
    {
        if(MillerRobbin(i)!=isprim[i])
            cout<<i<<endl;
    }
}

原来的这个是抄黑书上的,貌似只是用费马小定理来检验的,下面的这个应该才是正确的吧,正确率确实很高:

bool MillerRobbin(int n)
{
    if(n==2) return 1;
    else if((n&1)==0) return 0;
    int a,d;
    long long t;
    for(int i=0;i<s;i++)
    {
        a=rand()%(n-1)+1;
        d=n-1;
        while((d&1)==0) d>>=1;
        t=modexp(a,d,n);
        while(d!=n-1&&t!=1&&t!=n-1)
        {
            t=(t*t)% n;
            d<<=1;
        }
        if(t==n-1||(d&1)==1) continue;
        else return 0;
    }
    return 1;
}
Small_feed 评论 (29)
1
[回复]
saintqdd 说:
2010年8月19日 16:39

你写的素数测试似乎是有问题的。按照维基百科上的，同样取20次的循环；
29341的测试就有2次是失败的，即它不是质数，缺给出质数的结果。
而维基上的，确实全部通过

2
[回复]
Avatar_small
scturtle 说:
2010年8月26日 08:45

是wikipedia里http://zh.wikipedia.org/zh-cn/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E6%A3%80%E9%AA%8C这一篇吗?貌似算法不太一样.

3
[回复]
3214668848 说:
2010年10月08日 00:49

你可能没注意到数表示成a^(2^r*d)还有那个2^r，所以还要判断开方后的各种形式，详细可以参看这篇文章http://www.matrix67.com/blog/archives/234

5
[回复]
JSC Result Comilla B 说:
2022年8月28日 16:58

Comilla board is another education board working under Secondary and Higher Secondary Education, Bangladesh, and the education board is also successfully completed the Grade 8 terminal examinations at all selected examination test centers at Comilla division, and the Junior School Certificate and Junior Dakhil Certificate terminal examination is a second largest examination in the country. JSC Result Comilla Board The Comilla Board is also completed those subject wise exams between 1st to 3rd week of November as per schedule announced by School Education department, and there are a huge number of students are participated like as all other educational boards from all districts of the division, right now they are waiting to check JSC & JDC Result 2022 Comilla Board with subject wise marks and total marksheet with final CGPA grade of the student.

6
[回复]
civaget 说:
2023年12月08日 06:05

백링크하이 truly transformed my SEO game! Quality over quantity – exactly what my website needed.

7
[回复]
civaget 说:
2023年12月09日 22:23

티비몬 is a fresh start for Korean streaming, offering something for everyone.

8
[回复]
civaget 说:
2023年12月10日 18:31

 

I've found insightful answers to my questions on 달리머넷. It's a community that values expertise and helpfulness.

9
[回复]
civaget 说:
2023年12月10日 19:04

I had a great experience with 청주공항렌트카 Rental Mall 114. Highly recommended!

10
[回复]
civaget 说:
2023年12月11日 21:05

Thanks to 오피가이드, I've found my favorite OP spot. Their detailed information and reviews are unbeatable.

11
[回复]
civaget 说:
2023年12月12日 00:03

Experience the transformative power of 테라피 and embrace a life of balance and vitality.

12
[回复]
civaget 说:
2023年12月14日 18:51

제주오피 is a top choice for travelers. It offers a unique fusion of work and leisure on Jeju Island.

13
[回复]
civaget 说:
2023年12月16日 13:05

You have remarked very interesting points ! ps nice site. 축구중계

14
[回复]
SEO 说:
2023年12月16日 22:12

Toto Match sets the standard for 메이저사이트 security. Bet with confidence, knowing your safety is their priority.

15
[回复]
civaget 说:
2023年12月17日 18:26

I've shared 누누티비 with my colleagues, and they're now devoted users.

16
[回复]
civaget 说:
2023年12月17日 23:05

Don't miss out on 강남휴게텔. Your well-being deserves the exceptional relaxation and rejuvenation it offers in Gangnam.

17
[回复]
civaget 说:
2023年12月19日 21:12

Don't underestimate the value of free survey sites like 설문조사 사이트 무료 – they can be game-changers for your research and business growth.

18
[回复]
civaget 说:
2023年12月23日 15:16

If you're in need of relaxation, 러시아마사지 is the answer. I felt rejuvenated and stress-free.

19
[回复]
civaget 说:
2023年12月27日 04:24

The flexibility to experiment with book pricing during promotions or sales is a key advantage of self-publishing. self publishing

20
[回复]
civaget 说:
2023年12月28日 21:21

홍대 노래방is where the party's at in Hongdae. It's affordable, fun, and the song selection is endless.

21
[回复]
boardmodelpaper.com 说:
2024年1月02日 17:19

The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.

22
[回复]
civaget 说:
2024年1月15日 16:20

The next time I just read a blog, I hope which it doesnt disappoint me just as much as brussels. After all, It was my replacement for read, but I actually thought youd have something interesting to talk about. All I hear can be a number of whining about something that you could fix in the event you werent too busy trying to find attention. เว็บบอลคืนยอดเสีย

23
[回复]
pavzi.com 说:
2024年1月18日 01:30

Pavzi.com is a startup by passionate webmasters and bloggers who have a passion for providing engaging content that is accurate, interesting, and worthy to read. pavzi.com We are more like a web community where you can find different information, resources, and topics on day-to-day incidents or news. We provide you with the finest web content on every topic possible with the help of the editorial and content team.

24
[回复]
SEO 说:
2024年1月24日 17:28

Pretty nice post. I just stumbled upon your blog and wanted to say that I have really enjoyed browsing your blog posts. In any case I’ll be subscribing to your feed and I hope you write again soon The Presidential Family

25
[回复]
seo 说:
2024年2月11日 13:00

if the buffalo in my head could speak german i would not know a god damm thing. What i do know is that the language of art is out of this world. 룸싸롱정의

26
[回复]
sar 说:
2024年2月12日 18:02

Very good points you wrote here..Great stuff...I think you've made some truly interesting points.Keep up the good work. fc sevilla

27
[回复]
sar 说:
2024年2月21日 13:24

aa den stora boken… [...]p Have you noticed any performance problems with the wordpress platform? I ha oj[...]… 안전놀이터

28
[回复]
먹튀검증사이트 说:
2024年3月02日 14:31

That is the appropriate blog for anyone who desires to search out out about this topic. You realize a lot its nearly onerous to argue with you (not that I really would want…HaHa). You definitely put a brand new spin on a topic thats been written about for years. Nice stuff, just nice!

29
[回复]
flower shops in abu 说:
2024年3月14日 02:52

This article gives the light in which we can observe the reality. This is very nice one and gives indepth information. Thanks for this nice article.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter