Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Prime number formula


  • Please log in to reply
8 replies to this topic

#1 Hacker4life

Hacker4life

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 77 posts
  • Location:Serbia
  • Programming Language:C, C++, Delphi/Object Pascal, Pascal, Others
  • Learning:C, Java, C++, (Visual) Basic, Python, Delphi/Object Pascal, Pascal, Assembly, Others

Posted 11 August 2012 - 01:40 AM

hi, i was wondering if there is a prime number fomula.
My task is for 2 given numbers, to write all prime numbers between them.
  • 0

#2 Tonchi

Tonchi

    Helping the world with programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1249 posts
  • Location:Zagreb
  • Programming Language:C#, Others
  • Learning:C, C++, Python, JavaScript, Transact-SQL, Assembly

Posted 11 August 2012 - 01:58 AM

Check this link http://www.cplusplus...m/general/1125/
It is written in C++ but you should get the logic for getting prime numbers
  • 0

Microsoft Student Partner, Microsoft Certified Professional


#3 Hacker4life

Hacker4life

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 77 posts
  • Location:Serbia
  • Programming Language:C, C++, Delphi/Object Pascal, Pascal, Others
  • Learning:C, Java, C++, (Visual) Basic, Python, Delphi/Object Pascal, Pascal, Assembly, Others

Posted 11 August 2012 - 02:04 AM

yes, i knew that, but i thought there was a formula.
  • 0

#4 Tonchi

Tonchi

    Helping the world with programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1249 posts
  • Location:Zagreb
  • Programming Language:C#, Others
  • Learning:C, C++, Python, JavaScript, Transact-SQL, Assembly

Posted 11 August 2012 - 02:34 AM

There is no formula. Just checking solutions for each number.
  • 0

Microsoft Student Partner, Microsoft Certified Professional


#5 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 11 August 2012 - 05:37 AM

There is more a brute force approach that involves checking divisibility of all numbers < the number to check up to the square root. There is another approach using the Sieve of Eratosthenes... have a look it's a lot more efficient (timewise) than the naive approach.
  • 0

#6 Orjan

Orjan

    CC Mentor

  • Moderator
  • 2918 posts
  • Location:Karlstad, Sweden
  • Programming Language:C, Java, C++, C#, PHP, JavaScript, Pascal
  • Learning:Java, C#

Posted 11 August 2012 - 06:13 AM

You actually only have to check divisibility of the prime numbers up to the square root.
If you want to simplify the algorithm, check only odd numbers as an even number (besides 2) can not be a prime number.
  • 0

I'm a System developer at XLENT Consultant Group mainly working with SugarCRM.
Please DO NOT send mail or PM to me with programming questions, post them in the appropriate forum instead, where I and others can answer you.


#7 Luthfi

Luthfi

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1320 posts
  • Programming Language:PHP, Delphi/Object Pascal, Pascal, Transact-SQL
  • Learning:C, Java, PHP

Posted 11 August 2012 - 06:33 AM

There are lots of algorithm to fast find prime numbers. For example:

And there are still other algorithms available for testing. See them here. But many agree that the fastest algorithm is the Sieve of Atkin. However for small range I don't think it will give significant increase of speed.
  • 0

#8 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 11 August 2012 - 05:51 PM

There are some formulas that are guaranteed to generate prime numbers, but not all. There are also primality tests that will determine with high accuracy whether a number is prime or composite. In general, however, there is no formula for them.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#9 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 11 August 2012 - 06:09 PM

Cool, didn't know that. I found this: en.wikipedia.org/wiki/Formula_for_primes
Look at the recurrence relation. The article claims that the sequence contains only primes and 1s. It linked to a proof which I haven't looked at but assuming this is true then you can use the reccurence to generate so many numbers and put them into a set. Put the numbers into a set and remove 1 from that set to get a set of primes.

This is neat - though it doesn't appear useful if you want all prime numbers up to some number n.
  • 1




Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download