Register and join over 40,000 other developers!
Recent Topics

Learn algorithms and programming concepts
johnnylo  Apr 23 2019 07:49 AM

Job Gig PHP Form Needed
PJohnson  Apr 18 2019 03:55 AM

How to make code run differently depending on the platform it is running on?
xarzu  Apr 05 2019 09:17 AM

How do I set a breakpoint in an attached process in visual studio
xarzu  Apr 04 2019 11:47 AM
Recent Blog Entries
Recent Status Updates
Popular Tags
 networking
 Managed C++
 stream
 console
 database
 authentication
 Visual Basic 4 / 5 / 6
 session
 Connection
 asp.net
 import
 syntax
 hardware
 html5
 array
 mysql
 java
 php
 c++
 string
 C#
 html
 loop
 timer
 jquery
 ajax
 javascript
 programming
 android
 css
 assembly
 c
 form
 vb.net
 xml
 linked list
 login
 encryption
 pseudocode
 calculator
 sql
 setup
 help
 python
 game
 combobox
 binary
 hello world
 grid
 innerHTML
Prime number formula
Started by Hacker4life, Aug 11 2012 01:40 AM
8 replies to this topic
#1
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.
My task is for 2 given numbers, to write all prime numbers between them.
#2
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
It is written in C++ but you should get the logic for getting prime numbers
Microsoft Student Partner, Microsoft Certified Professional
#3
Posted 11 August 2012  02:04 AM
yes, i knew that, but i thought there was a formula.
#4
Posted 11 August 2012  02:34 AM
There is no formula. Just checking solutions for each number.
Microsoft Student Partner, Microsoft Certified Professional
#5
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.
#6
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.
If you want to simplify the algorithm, check only odd numbers as an even number (besides 2) can not be a prime number.
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
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.
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.
#8
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.
Programming is a branch of mathematics.
My CodeCall Blog  My Personal Blog
My MineCraft server site: http://banishedwings.enjin.com/
#9
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.
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.
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download