• <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>

            C++研究

            C++細節深度探索及軟件工程

              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              37 隨筆 :: 0 文章 :: 74 評論 :: 0 Trackbacks


            1.GRIDDLE METHOD (ALSO CALLED SIFT METHOD)

            When I was a student in Bachelor phrase , a teacher has tought me a method called griddle method , it's principle is:

            if a number can be devided by another number(except 1) , it isn't a prime , so , we set the non-prime at zero. after all number [In fact , half of the range checked is OK ]test finished , We simply output the NON-ZERO number , it 's the prime table in the RANGE.

            E.G
            Define the Range from 1-100;

            /********************************************************************
             created: 2007/04/19
             created: 19:4:2007   3:00
             filename:  C:\testvc6\TestStll\TestStll.cpp
             file path: C:\testvc6\TestStll
             file base: TestStll
             file ext: cpp
             author:  Chang xinglong(King.C)
             purpose: Print Prime Table in RANGE(1-100)
            *********************************************************************/

            The Code Here :

             


            #include 
            <iostream>
            #include 
            <algorithm>
            #include 
            <vector>
            using namespace std;

            void InitArray(int A[] ,int len)
            {
                
            for (int i=0;i<len;i++)
                
            {
                    A[i]
            =i+1;
                }

            }


            void OutputPrime(int A[] ,int len)
            {
              
            for (int i=2;i<len;i++)
              
            {
                  
            for (int j=2;i*j<=len;j++)
                  
            {
                      A[i
            *j-1]=0;
                      cout
            <<i<<","<<j<<","<<i*j<<endl;
                  }

                 
              }

              
            for (i=0;i<len;i++)
              
            {
                  
            if (A[i]!=0)
                  
            {
                      cout
            <<A[i]<<" ";
                  }

                  
              }

              cout
            <<endl;
            }

            // Main Method [4/19/2007 Changxinglong (King.C)]
            int main(int argc, char* argv[])
            {
                
            int A[100];
                InitArray(A,
            100);
                OutputPrime(A,
            100);
                
            return 1;
            }




             2.THE DIRECT METHOD

            E.G

            /********************************************************************
             created: 2007/04/19
             created: 19:4:2007   3:00
             filename:  C:\testvc6\TestStll\TestStll.cpp
             file path: C:\testvc6\TestStll
             file base: TestStll
             file ext: cpp
             author:  Chang xinglong(King.C)
             purpose: Prime ?
            *********************************************************************/

            Here is the Kernel Function(Quote : STL TURORIAL REFERRENCE):

             

             1//predicate, which returns whether an integer is a prime number
             2bool isPrime (int number)
             3{
             4//ignore negative sign
             5number = abs(number);
             6// 0 and 1 are prime numbers
             7if (number == 0 || number == 1{
             8return true;
             9}

            10//find divisor that divides without a remainder
            11int divisor;
            12for (divisor = number/2; number%divisor != 0--divisor) {
            13;
            14}

            15//if no divisor greater than 1 is found, it is a prime number
            16return divisor == 1;
            17}


            In Main Function , traverse the given range judge every number use the above function:

            int main(int argc , char * argv[])
            {
              
            int A[100];
              InitArray(A,
            100);
              
            for(int i=0;i<100;i++)
                
            if(isPrime(A[i]))
                   cout
            <<A[i]<<endl;
            }

            3. Extention
             Further , if  there is a given List or Vector and it's filled with data , how can you find the prime number in the data effiectly ?
            STL Algorithm can help you indeed. After the step two , we can write a few code to implement the function:
            int main()
            {
            list
            <int> coll;
            //insert elements from 1 to 100
            for (int i=1; i<=100++i) {
            coll.push_back(i);
            }

            //search for prime number
            list<int>::iterator pos;
            pos 
            = find_if (coll.begin(), coll.end(), //range
            isPrime); //predicate
            if (pos != coll.end()) {
            //found
            cout << *pos << " is first prime number found" << endl;
            }

            else {
            //not found
            cout << "no prime number found" << endl;
            }

            }


            posted on 2007-04-19 03:05 常興龍 閱讀(1343) 評論(8)  編輯 收藏 引用 所屬分類: Algorithm

            評論

            # re: Some algorithms about judging a prime . 2007-04-19 10:58 uglystone
            Write well!
            I think tha IsPrime funtion shoule be implemented as a functors!
            it may be more elegant!
            class IsPrime{
            public:
            IsPrime(){
            }
            bool isPrime (int number)
            {
            .....
            }
            };  回復  更多評論
              

            # re: Some algorithms about judging a prime . 2007-04-19 22:18 chenger
            這應該是最原始的辦法  回復  更多評論
              

            # re: Some algorithms about judging a prime . 2007-04-26 19:00 oyjpart
            有一些很好的隨機算法  回復  更多評論
              

            # re: Some algorithms about judging a prime . 2007-05-12 23:26 不是很懂
            A primality test is a test to determine whether or not a given number is prime, as opposed to actually decomposing the number into its constituent prime factors (which is known as prime factorization).

            Primality tests come in two varieties: deterministic and probabilistic. Deterministic tests determine with absolute certainty whether a number is prime. Examples of deterministic tests include the Lucas-Lehmer test and elliptic curve primality proving. Probabilistic tests can potentially (although with very small probability) falsely identify a composite number as prime (although not vice versa). However, they are in general much faster than deterministic tests. Numbers that have passed a probabilistic prime test are therefore properly referred to as probable primes until their primality can be demonstrated deterministically.

            A number that passes a probabilistic test but is in fact composite is known as a pseudoprime. There are many specific types of pseudoprimes, the most common being the Fermat pseudoprimes, which are composites that nonetheless satisfy Fermat's little theorem.

            The Rabin-Miller strong pseudoprime test is a particularly efficient test. Mathematica versions 2.2 and later have implemented the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test as the primality test used by the function PrimeQ[n]. Like many such algorithms, it is a probabilistic test using pseudoprimes. In order to guarantee primality, a much slower deterministic algorithm must be used. However, no numbers are actually known that pass advanced probabilistic tests (such as Rabin-Miller) yet are actually composite.

            The state of the art in deterministic primality testing for arbitrary numbers is elliptic curve primality proving. As of 2004, the program PRIMO can certify a 4769-digit prime in approximately 2000 hours of computation (or nearly three months of uninterrupted computation) on a 1 GHz processor using this technique.

            Unlike prime factorization, primality testing was long believed to be a P-problem (Wagon 1991). This had not been demonstrated, however, until Agrawal et al. (2002) unexpectedly discovered a polynomial time algorithm for primality testing that has asymptotic complexity of (Bernstein 2002, Clark 2002, Indian Institute of Technology 2002, Pomerance 2002ab, Robinson 2002). Their algorithm has come to be called the AKS primality test.

            http://mathworld.wolfram.com/PrimalityTest.html  回復  更多評論
              

            # re: Some algorithms about judging a prime . 2007-05-17 00:12 天津大學計算機學院 常興龍
            Very appreciated for your comment , I have benefited a lot from it. thanks again!  回復  更多評論
              

            # re: Some algorithms about judging a prime . 2008-04-24 02:01 Rex.Kingsir
            Thanks a lot for talk so much!  回復  更多評論
              

            # re: Some algorithms about judging a prime . 2008-07-05 16:45 我們一起來提高
            數論學家利用費馬小定理研究出了多種素數測試方法,目前最快的算法是拉賓米
            勒測試算法,其過程如下:
            (1)計算奇數M,使得N=(2**r)*M+1
            (2)選擇隨機數A<N
            (3)對于任意i<r,若A**((2**i)*M) MOD N = N-1,則N通過隨機數A的測試
            (4)或者,若A**M MOD N = 1,則N通過隨機數A的測試
            (5)讓A取不同的值對N進行5次測試,若全部通過則判定N為素數
            若N 通過一次測試,則N 不是素數的概率為 25%,若N 通過t 次測試,則N 不是
            素數的概率為1/4**t。事實上取t 為5 時,N 不是素數的概率為 1/128,N 為素數的
            概率已經大于99.99%。
            在實際應用中,可首先用300—500個小素數對N 進行測試,以提高拉賓米勒測試
            通過的概率,從而提高測試速度。而在生成隨機素數時,選取的隨機數最好讓 r=0,
            則可省去步驟(3) 的測試,進一步提高測試速度
              回復  更多評論
              

            # re: Some algorithms about judging a prime . 2009-05-16 19:29 u2u
            @我們一起來提高
            現在最快的是AKS...  回復  更多評論
              

            > hi的博客
            午夜福利91久久福利| 久久精品国产亚洲av影院| 久久综合九色综合久99| 国产精品美女久久久| 亚洲嫩草影院久久精品| 久久无码国产| 久久精品国产精品亚洲毛片| 九九99精品久久久久久| 久久综合色之久久综合| 久久国产乱子伦免费精品| 国产亚州精品女人久久久久久 | 三级三级久久三级久久| 久久久一本精品99久久精品88| 国产精品久久久久无码av| 久久久久国产| 久久精品国产亚洲AV无码偷窥| 精品欧美一区二区三区久久久| 亚洲中文字幕无码久久精品1| 久久精品无码免费不卡| 无码国内精品久久人妻蜜桃| 久久久网中文字幕| 国产精品久久亚洲不卡动漫| 精品久久久久久中文字幕大豆网| 国产91久久综合| 99麻豆久久久国产精品免费| 无码日韩人妻精品久久蜜桃| 伊人久久精品影院| 久久综合九色综合欧美就去吻| 久久免费高清视频| 久久综合亚洲欧美成人| 久久无码专区国产精品发布| 一极黄色视频久久网站| 久久嫩草影院免费看夜色| 成人精品一区二区久久久| 久久国产精品-国产精品| 97久久精品无码一区二区天美| 久久中文骚妇内射| 久久久一本精品99久久精品66| 久久精品99久久香蕉国产色戒| 精品久久久久久国产潘金莲| 国产V综合V亚洲欧美久久|