• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            poj 1811 Prime Test 數論 素數測試

             代碼如下:
            #include <stdio.h>
            #include <time.h>
            #include <math.h>
            #include <stdlib.h>
            #include <algorithm>
            using namespace std;
            typedef unsigned long long LL;
            #define MAX (5000000)
            bool bPrime[MAX];
            void InitPrime()
            {
                int nMax = sqrt((double)MAX) + 1;
                bPrime[0] = bPrime[1] = true;
                for (int i = 2; i <= nMax; ++i)
                {
                    if (!bPrime[i])
                    {
                        for (int j = 2 * i; j < MAX; j += i)
                        {
                            bPrime[j] = true;
                        }
                    }
                }
            }
            LL multAndMod(LL a, LL b, LL n)
            {
                LL tmp = 0;
                while (b)
                {
                    if(b & 1)
                    {
                        tmp = (tmp + a) % n;
                    }
                    a = (a << 1) % n;
                    b >>= 1;
                }
                return tmp;
            }
            //計算a^u%n
            LL ModExp(LL a, LL u, LL n)
            {
                LL d = 1;
                a %= n;
                while (u)
                {
                    if (u & 1)
                    {
                        d = multAndMod(d, a, n);
                    }
                    a = multAndMod(a, a, n);
                    u >>= 1;
                }
                return d % n;
            }
            //判斷nN是不是合數
            bool Witness(LL a, LL nN)
            {
                LL u = nN - 1, t = 0;//將nN-1表示為u*2^t
                while (u % 2 == 0)
                {
                    t++;
                    u >>= 1;
                }
                LL x0 = ModExp(a, u, nN);//x是a^u
                LL x1;
                for (int i = 1; i <= t; ++i)
                {
                    x1 = multAndMod(x0, x0, nN);
                    if (x1 == 1 && x0 != nN - 1 && x0 != 1)
                    {
                        return true;
                    }
                    x0 = x1;
                }
                if (x1 != 1)
                {
                    return true;
                }
                return false;
            }
            //素數測試
            bool MillerRabin(LL nN)
            {
                //if (nN < MAX)return !bPrime[nN];
                const int TIME = 10;
                for (int i = 0; i < TIME; ++i)
                {
                    LL a = rand() % (nN - 1) + 1;
                    if (Witness(a, nN))
                    {
                        return false;
                    }
                }
                return true;
            }
            LL gcd(LL a, LL b)
            {
                if (a < b)swap(a, b);
                while (b)
                {
                    LL t = a;
                    a = b;
                    b = t % b;
                }
                return a;
            }
            //啟發式尋找nN的因子
            LL PollardRho(LL n, LL c)
            {
                LL i = 1, t = 2;
                LL x, y;
                LL ans;
                srand(time(NULL));  
                y = x = rand() % n;
                while(1)
                {
                    i++;
                    x = (multAndMod(x, x, n) + c) % n;
                    ans = gcd(y - x, n);
                    if(ans > 1 && ans < n)
                        return ans;
                    if(x == y)
                        return n;
                    if(t == i)
                    {
                        y = x;
                        t <<= 1;
                    }
                }
            }
            LL FindMin(LL nN, LL c)
            {
                //printf("nN:%I64u\n", nN);
                if (MillerRabin(nN) || nN <= 1)
                {
                    return nN;
                }
                LL p = nN;
                while (p >= nN) p = PollardRho(p, c--);
                if (p > 1)
                    p = FindMin(p, c);//分解p的最小因子
                if (p < nN)
                {
                    LL q = nN / p;
                    q = FindMin(q, c);//找到q的最小因子
                    p = min(p, q);
                }
                return p;
            }
            int main()
            {
                int nTest;
                srand(time(NULL));
                //InitPrime();
                scanf("%d", &nTest);
                while (nTest--)
                {
                    LL nN;
                    scanf("%I64u", &nN);
                    if (nN > 2 && nN % 2 == 0)
                    {
                        printf("2\n");
                    }
                    else if (nN == 2 || MillerRabin(nN))
                    {
                        printf("Prime\n");
                    }
                    else
                    {
                        printf("%I64u\n", FindMin(nN, 181));
                    }
                }
                return 0;
            }

            posted on 2012-09-24 12:56 yx 閱讀(199) 評論(0)  編輯 收藏 引用 所屬分類: 數論

            <2012年10月>
            30123456
            78910111213
            14151617181920
            21222324252627
            28293031123
            45678910

            導航

            統計

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學

            網友

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            色综合久久天天综合| 97久久久久人妻精品专区| AV无码久久久久不卡网站下载| 久久se这里只有精品| 色青青草原桃花久久综合| 久久伊人色| 久久婷婷五月综合成人D啪| 久久青青草视频| 婷婷久久香蕉五月综合加勒比| 久久99精品久久久久久齐齐| 91精品国产综合久久久久久| 久久精品国产亚洲av麻豆色欲| 国产精品久久久久久吹潮| 国产午夜精品理论片久久影视| 91精品国产91久久综合| 国产精品久久久久aaaa| 久久综合一区二区无码| 日韩精品无码久久久久久| 色综合色天天久久婷婷基地| 色婷婷综合久久久中文字幕| 国产亚洲精久久久久久无码77777 国产亚洲精品久久久久秋霞 | 少妇无套内谢久久久久| 一本大道久久东京热无码AV| 久久亚洲av无码精品浪潮| 久久国产综合精品五月天| 亚洲国产精品久久久久网站| 久久精品国产久精国产| 久久精品无码一区二区无码| 国产亚洲成人久久| 欧美精品丝袜久久久中文字幕| 国产精品va久久久久久久| 日韩精品久久久久久久电影| 国产成人综合久久综合| 国产精品久久99| 精品无码久久久久久久久久| 婷婷综合久久中文字幕蜜桃三电影| 99久久免费只有精品国产| 一本色道久久88—综合亚洲精品| 久久精品国产亚洲av瑜伽| 国产精品久久成人影院| 成人国内精品久久久久影院|