Storing a "large" number of prime numbers

This is a discussion on Storing a "large" number of prime numbers within the General Discussions forums, part of the Community Boards category; I have been writing some c code to investigate the properties of prime numbers. Currently I have a function getPrimes(int ...

  1. #1
    Registered User javaeyes's Avatar
    Join Date
    Feb 2012
    Posts
    153

    Storing a "large" number of prime numbers

    I have been writing some c code to investigate the properties of prime numbers. Currently I have a function getPrimes(int primemax) which dynamically allocates memory for an array of the primes, so that primes[0]=2 , primes[1]=3 .... This has been working well, but I am going to need a more permanent and scalable way to store them as primemax grows large. I am not opposed to using some service (if such a service exists) or to writing my own code to possibly store them as a csv list.
    My future algorithm will constantly be needing to find primes[bignumber] where bignumber is the index of the primes array. The actual prime stored in that index will be even larger.
    Any thoughts appreciated. Thanks.

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,166
    Define what you mean by primemax being "large": how scalable do you need to be? Do you intend to go beyond what can be represented in a 32 bit unsigned int? Beyond what can be stored in a 64 bit unsigned integer?

    It has actually been proven that there is an infinite number of prime numbers i.e. whatever value you pick, there will be a larger prime value. The largest known primes have millions of decimal digits.
    Right 98% of the time, and don't care about the other 3%.

  3. #3
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  4. #4
    Registered User javaeyes's Avatar
    Join Date
    Feb 2012
    Posts
    153
    I will need go beyond 64 bit unsigned integers, so I will need to use some sort of additional library at the least. I am beginning to think python might be an easier road, i've read that the int datatype has an arbitrary size. I've just started to get dialed into c and feel that under the hood it will be better to do it with c though.
    And yes I am aware there are infinite primes, in fact it's one of my favorite proofs. (And possibly the only proof I have memorized)
    And so "large" will mean 50-100+ decimal digits (for the prime values) dwarfing the default data size for ints-- the indexes on the other hand should be ~2% of the largest prime I'll need.

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Can you let us in on the purpose of your secret project? You'll get more pertinent advice that way.

    Check out The GNU MP Bignum Library
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  6. #6
    Registered User javaeyes's Avatar
    Join Date
    Feb 2012
    Posts
    153
    I am trying to factor large semi-prime numbers (prime multiplied by a prime.) You can probably do the math, and I realize that this may all be in vain, but it's a lot of fun and I'm learning a ton about other things I would never come across. And for the record I am doing it as a purely academic pursuit (though not for credit) in the sense that I am not trying to factor any one particular number to crack it, but to look at properties of all semi primes. I realize there is a >99% chance I will not find an algorithm better than current sieves. But that doesn't mean you can't try.

  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I didn't mean to suggest that your efforts were futile. You sound like you understand the situation, and now we know exactly what you're trying to do.

    Check out that bignum library.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  8. #8
    Registered User javaeyes's Avatar
    Join Date
    Feb 2012
    Posts
    153
    Thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 31
    Last Post: 08-16-2011, 08:32 AM
  2. Replies: 31
    Last Post: 11-25-2009, 12:10 PM
  3. How to use "switch" to perform large numbers cases?
    By megablue in forum C Programming
    Replies: 4
    Last Post: 07-09-2003, 10:51 AM
  4. "itoa"-"_itoa" , "inp"-"_inp", Why some functions have "
    By L.O.K. in forum Windows Programming
    Replies: 5
    Last Post: 12-08-2002, 07:25 AM
  5. "CWnd"-"HWnd","CBitmap"-"HBitmap"...., What is mean by "
    By L.O.K. in forum Windows Programming
    Replies: 2
    Last Post: 12-04-2002, 06:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21