• <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++細(xì)節(jié)深度探索及軟件工程

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              37 隨筆 :: 0 文章 :: 74 評(píng)論 :: 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 常興龍 閱讀(1346) 評(píng)論(8)  編輯 收藏 引用 所屬分類: Algorithm

            評(píng)論

            # 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)
            {
            .....
            }
            };  回復(fù)  更多評(píng)論
              

            # re: Some algorithms about judging a prime . 2007-04-19 22:18 chenger
            這應(yīng)該是最原始的辦法  回復(fù)  更多評(píng)論
              

            # re: Some algorithms about judging a prime . 2007-04-26 19:00 oyjpart
            有一些很好的隨機(jī)算法  回復(fù)  更多評(píng)論
              

            # 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  回復(fù)  更多評(píng)論
              

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

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

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

            # re: Some algorithms about judging a prime . 2009-05-16 19:29 u2u
            @我們一起來提高
            現(xiàn)在最快的是AKS...  回復(fù)  更多評(píng)論
              

            > hi的博客
            久久久精品久久久久久 | 日韩一区二区久久久久久| 亚洲va中文字幕无码久久不卡| 久久久久无码精品国产不卡| 久久精品亚洲中文字幕无码麻豆| 国产精品久久久久影院嫩草| 大美女久久久久久j久久| 无码8090精品久久一区| 久久亚洲美女精品国产精品| 久久综合丁香激情久久| 亚洲色欲久久久久综合网 | 久久精品嫩草影院| 亚洲精品第一综合99久久| 亚洲综合熟女久久久30p| 青青草国产精品久久久久| 综合久久给合久久狠狠狠97色| 久久久国产乱子伦精品作者| 久久久久久青草大香综合精品| 色狠狠久久AV五月综合| 久久艹国产| AV狠狠色丁香婷婷综合久久| 亚洲一区精品伊人久久伊人| 69SEX久久精品国产麻豆| 久久受www免费人成_看片中文| 久久免费国产精品一区二区| 亚洲乱码中文字幕久久孕妇黑人| 久久精品国产亚洲7777| 久久夜色精品国产噜噜噜亚洲AV| 日本久久中文字幕| 国内精品久久久久久久久| 久久99国产综合精品| 国内高清久久久久久| 国产精品久久久久a影院| 女同久久| 伊人久久国产免费观看视频| 久久久黄片| 久久亚洲中文字幕精品一区四 | 7777精品久久久大香线蕉| 内射无码专区久久亚洲| 精品无码人妻久久久久久| 国内精品免费久久影院|