Loading ...
Sorry, an error occurred while loading the content.
 

Program for testing small numbers

Expand Messages
  • Gary Chaffey
    Could somebody recommend a program that can PRP test large numbers of small numbers (say under 25 digits). I know PFGW will do this but is there a faster
    Message 1 of 8 , Sep 2, 2004
      Could somebody recommend a program that can PRP test large numbers of small numbers (say under 25 digits). I know PFGW will do this but is there a faster program for small numbers?
      Regards
      Gary


      ---------------------------------
      ALL-NEW Yahoo! Messenger - all new features - even more fun!

      [Non-text portions of this message have been removed]
    • andrew_j_walker
      ... of small numbers (say under 25 digits). I know PFGW will do this but is there a faster program for small numbers? ... It might be worth testing pari, as
      Message 2 of 8 , Sep 2, 2004
        --- In primenumbers@yahoogroups.com, Gary Chaffey <garychaffey2@y...>
        wrote:
        > Could somebody recommend a program that can PRP test large numbers
        of small numbers (say under 25 digits). I know PFGW will do this but
        is there a faster program for small numbers?
        > Regards
        > Gary
        >
        >

        It might be worth testing pari, as it's meant to be quite fast
        with mod-power operations. However if you're performing trial
        division as well it may not be as fast.

        Andrew
      • Bigfoot
        I did a quick scan of the files and didn t see a sieve for finding small primes. I may have missed one if it was there, can someone give me a link to one
        Message 3 of 8 , Sep 2, 2004
          I did a quick scan of the files and didn't see a sieve for finding
          small primes. I may have missed one if it was there, can someone
          give me a link to one (written in c or c++)
        • Milton Brown
          A program in Java (C++) for small primes is attached. Milton L. Brown miltbrown at earthlink.net public class Prime { public static void main(String[] args) {
          Message 4 of 8 , Sep 2, 2004
            A program in Java (C++) for small primes is attached.

            Milton L. Brown
            miltbrown at earthlink.net

            public class Prime
            {
            public static void main(String[] args)
            {

            int i, j, k;
            for (i = 2; i<3000; i++)
            { k = 1;
            for ( j=2; j<i; j++) {
            k = i %j;
            if (k == 0) break;
            }
            if ((i% 50)==0) System.out.println(" ");
            if (k !=0) System.out.print(i+" ");

            };

            }
            }


            > [Original Message]
            > From: Bigfoot <plano9@...>
            > To: <primenumbers@yahoogroups.com>
            > Date: 9/2/2004 5:48:35 PM
            > Subject: [PrimeNumbers] Re: Program for testing small numbers
            >
            > I did a quick scan of the files and didn't see a sieve for finding
            > small primes. I may have missed one if it was there, can someone
            > give me a link to one (written in c or c++)
            >
            >
            >
            >
            > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
            > The Prime Pages : http://www.primepages.org/
            >
            >
            > Yahoo! Groups Links
            >
            >
            >
            >
          • Bigfoot
            I m working on turning that into c++ code that I can use, but I don t see what the purpose of the lines k!==0 //pointless, no need to do factorial here and
            Message 5 of 8 , Sep 3, 2004
              I'm working on turning that into c++ code that I can use, but I don't
              see what the purpose of the lines
              k!==0 //pointless, no need to do factorial here
              and
              i%50 //wouldn't that be if the remainder is 50?

              --- In primenumbers@yahoogroups.com, "Milton Brown" <miltbrown@e...>
              wrote:
              > A program in Java (C++) for small primes is attached.
              >
              > Milton L. Brown
              > miltbrown at earthlink.net
              >
              > public class Prime
              > {
              > public static void main(String[] args)
              > {
              >
              > int i, j, k;
              > for (i = 2; i<3000; i++)
              > { k = 1;
              > for ( j=2; j<i; j++) {
              > k = i %j;
              > if (k == 0) break;
              > }
              > if ((i% 50)==0) System.out.println(" ");
              > if (k !=0) System.out.print(i+" ");
              >
              > };
              >
              > }
              > }
              >
              >
              > > [Original Message]
              > > From: Bigfoot <plano9@y...>
              > > To: <primenumbers@yahoogroups.com>
              > > Date: 9/2/2004 5:48:35 PM
              > > Subject: [PrimeNumbers] Re: Program for testing small numbers
              > >
              > > I did a quick scan of the files and didn't see a sieve for
              finding
              > > small primes. I may have missed one if it was there, can someone
              > > give me a link to one (written in c or c++)
              > >
              > >
              > >
              > >
              > > Unsubscribe by an email to: primenumbers-
              unsubscribe@yahoogroups.com
              > > The Prime Pages : http://www.primepages.org/
              > >
              > >
              > > Yahoo! Groups Links
              > >
              > >
              > >
              > >
            • Hadley, Thomas H (Tom), ALABS
              ... First of all, he wrote k != 0 , not k !== 0 and the first is basic C/C++ code. There is no confusion with the factorial. ... No, it s the remainder
              Message 6 of 8 , Sep 3, 2004
                Bigfoot wrote:

                >> k!==0 //pointless, no need to do factorial here

                First of all, he wrote "k != 0", not "k !== 0" and the first is
                basic C/C++ code. There is no confusion with the factorial.

                >>i%50 //wouldn't that be if the remainder is 50?

                No, it's the remainder after dividing by 50.

                Please read a book on intro to C or C++ before questioning someone's program. It looks to me like Milton's program is a valid, if inefficient, prime number generator.

                Tom Hadley

                -----Original Message-----
                From: Bigfoot [mailto:plano9@...]
                Sent: Friday, September 03, 2004 5:56 PM
                To: primenumbers@yahoogroups.com
                Subject: [PrimeNumbers] Re: Program for testing small numbers


                I'm working on turning that into c++ code that I can use, but I don't
                see what the purpose of the lines
                k!==0 //pointless, no need to do factorial here

                and
                i%50 //wouldn't that be if the remainder is 50?

                --- In primenumbers@yahoogroups.com, "Milton Brown" <miltbrown@e...>
                wrote:
                > A program in Java (C++) for small primes is attached.
                >
                > Milton L. Brown
                > miltbrown at earthlink.net
                >
                > public class Prime
                > {
                > public static void main(String[] args)
                > {
                >
                > int i, j, k;
                > for (i = 2; i<3000; i++)
                > { k = 1;
                > for ( j=2; j<i; j++) {
                > k = i %j;
                > if (k == 0) break;
                > }
                > if ((i% 50)==0) System.out.println(" ");
                > if (k !=0) System.out.print(i+" ");
                >
                > };
                >
                > }
                > }
                >
                >
                > > [Original Message]
                > > From: Bigfoot <plano9@y...>
                > > To: <primenumbers@yahoogroups.com>
                > > Date: 9/2/2004 5:48:35 PM
                > > Subject: [PrimeNumbers] Re: Program for testing small numbers
                > >
                > > I did a quick scan of the files and didn't see a sieve for
                finding
                > > small primes. I may have missed one if it was there, can someone
                > > give me a link to one (written in c or c++)
                > >
                > >
                > >
                > >
                > > Unsubscribe by an email to: primenumbers-
                unsubscribe@yahoogroups.com
                > > The Prime Pages : http://www.primepages.org/
                > >
                > >
                > > Yahoo! Groups Links
                > >
                > >
                > >
                > >




                Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
                The Prime Pages : http://www.primepages.org/


                Yahoo! Groups Links
              • Milton Brown
                For the small prime lister program, the outer for-loop is exited as soon as i is found to be composite. The number is not composite (prime) when k != 0,
                Message 7 of 8 , Sep 3, 2004
                  For the small prime lister program, the outer for-loop
                  is exited as soon as i is found to be composite. The
                  number is not composite (prime) when k != 0, otherwise it
                  is composite. This line is required to print the primes.

                  The line with (i % 50) = = 0 will print a line-return, with less
                  than 50 primes on a single line of out-put, so that many primes
                  can be seen on a single page.

                  Milton L. Brown
                  miltbrown at earthlink.net


                  > [Original Message]
                  > From: Bigfoot <plano9@...>
                  > To: <primenumbers@yahoogroups.com>
                  > Date: 9/3/2004 3:56:43 PM
                  > Subject: [PrimeNumbers] Re: Program for testing small numbers
                  >
                  > I'm working on turning that into c++ code that I can use, but I don't
                  > see what the purpose of the lines
                  > k!==0 //pointless, no need to do factorial here
                  > and
                  > i%50 //wouldn't that be if the remainder is 50?
                  >
                  > --- In primenumbers@yahoogroups.com, "Milton Brown" <miltbrown@e...>
                  > wrote:
                  > > A program in Java (C++) for small primes is attached.
                  > >
                  > > Milton L. Brown
                  > > miltbrown at earthlink.net
                  > >
                  > > public class Prime
                  > > {
                  > > public static void main(String[] args)
                  > > {
                  > >
                  > > int i, j, k;
                  > > for (i = 2; i<3000; i++)
                  > > { k = 1;
                  > > for ( j=2; j<i; j++) {
                  > > k = i %j;
                  > > if (k == 0) break;
                  > > }
                  > > if ((i% 50)==0) System.out.println(" ");
                  > > if (k !=0) System.out.print(i+" ");
                  > >
                  > > };
                  > >
                  > > }
                  > > }
                  > >
                  > >
                  > > > [Original Message]
                  > > > From: Bigfoot <plano9@y...>
                  > > > To: <primenumbers@yahoogroups.com>
                  > > > Date: 9/2/2004 5:48:35 PM
                  > > > Subject: [PrimeNumbers] Re: Program for testing small numbers
                  > > >
                  > > > I did a quick scan of the files and didn't see a sieve for
                  > finding
                  > > > small primes. I may have missed one if it was there, can someone
                  > > > give me a link to one (written in c or c++)
                  > > >
                  > > >
                  > > >
                  > > >
                  > > > Unsubscribe by an email to: primenumbers-
                  > unsubscribe@yahoogroups.com
                  > > > The Prime Pages : http://www.primepages.org/
                  > > >
                  > > >
                  > > > Yahoo! Groups Links
                  > > >
                  > > >
                  > > >
                  > > >
                  >
                  >
                  >
                  >
                  > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
                  > The Prime Pages : http://www.primepages.org/
                  >
                  >
                  > Yahoo! Groups Links
                  >
                  >
                  >
                  >
                • Jim Laird
                  Here s a simple, simple prime number tester for very small numbers. It saves the previous results of test searches in memory, so it will be impractical if you
                  Message 8 of 8 , Sep 7, 2004
                    Here's a simple, simple prime number tester for very small numbers. It
                    saves the previous results of test searches in memory, so it will be
                    impractical if you search for primes that are too large (depending on
                    how much memory is on your system). It also uses STL classes for
                    containers etc. Worked on my system. Change main() as required. Only
                    checks up to the square root of the test number as a slight
                    optimization.

                    Cheers, Jim

                    ========================================================================
                    =====

                    #include <string>
                    #include <vector>
                    #include <ostream>

                    using namespace std;

                    // loads the prime list with the initial primes
                    void preload_pl(vector<int> &v)
                    {
                    v.resize(6);
                    v[0]=2; v[1]=3; v[2]=5;
                    v[3]=7; v[4]=11; v[5]=13;
                    return;
                    }

                    // returns true if testnum is prime. Adds primes to v as necessary
                    bool test_prime(int testnum, vector<int> &v)
                    {
                    // check the first few primes
                    for (unsigned int i = 0; i < 5; i++)
                    if (testnum % v[i] == 0) return false;

                    // check the rest of the list
                    for (unsigned int i = 5; i < v.size(); i++) {
                    if (testnum % v[i] == 0) return false;
                    if (testnum < (v[i]*v[i])) return true;
                    }

                    // at the end of the prime list, increase it till you hit the
                    test
                    // or determine that testnum is composite

                    for(int x = v[v.size()-1] + 2; ; x += 2) {
                    if (test_prime(x, v) == true) {
                    v.push_back(x);
                    if (testnum % x == 0) return false;
                    if ((x*x) > testnum) return true;
                    }
                    }
                    }



                    void main(int argv, char **argc)
                    {
                    vector<int> base_primes;

                    // initialize vector
                    base_primes.reserve(1000); // make room for 1000
                    entries to begin with
                    preload_pl(base_primes); // initialize the prime
                    list

                    // sieve numbers between 1001 and 10000
                    cout << "Primes between 1001 and 10000\n";
                    for (int test = 1001; test < 10000; test += 2) {
                    if (test_prime(test, base_primes) == true) {
                    cout << test << ", ";
                    }
                    }

                    return;
                    }
                  Your message has been successfully submitted and would be delivered to recipients shortly.