| View previous topic - View next topic |
| Author |
Message |
Unknown
Moira's Silly Little Slave Bitch
Joined: 19 Jul 2005
Posts: 82
Location: Behind you...
|
 Posted: Tue Dec 05, 2006 1:45 pm Post subject: Primes!!! |
[quote] |
|
Here's a little C++ program that i wrote in like 5min to get prime numbers... Can ANYONE think of a better/faster method/algorithm...
| Code: |
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int MaxAmount = 0;
bool prime = true;
int main(){
ofstream PNS ("PrimeNumbers.dat");
cout << "Please give me a max number to get the primes up to: " <<endl>> MaxAmount;
for(int lp=0;lp<MaxAmount>1;lp1--){
if(lp % lp1 == 0){
prime = false;
}
}
if(prime){
PNS << lp << "\n";
}
prime = true;
}
PNS.close();
return 0;
}
|
P.S. I toke 50min to calculate all the primes between 0 and one million... (On a dual core 1.66Ghz, 1gb ram system)
Ohh and this stupid thing won't let me put << >> .... so, it's supposed to be cin >> MaxAmount; NOT endl>> MaxAmount...
_________________
Most people would succeed in small things if they were not troubled with such great ambitions.
|
|
| Back to top |
|
 |
Ninkazu
Demon Hunter
Joined: 08 Aug 2002
Posts: 945
Location: Location:
|
| Posted: Tue Dec 05, 2006 2:33 pm Post subject: |
[quote] |
|
|
I'm sure it's a fuckbunch more code, but Prime95 surely has a faster method, though it's only for Mersenne primes..
|
|
| Back to top |
|
|
Mokona
Pretty, Pretty Fairy Princess
Joined: 26 Jun 2003
Posts: 12
|
| Posted: Tue Dec 05, 2006 2:59 pm Post subject: Re: Primes!!! |
[quote] |
|
That code block seems quite broken:
| Code: | | for(int lp=0;lp<MaxAmount>1;lp1--){ |
doesn't look much like valid C++ code to me. And there appear to be a mismatched number of { and } :-P
Anyway, a couple of possible optimisations:
1) Break out of the is-this-this-a-prime inner loop once you've found it's not prime.
2) When checking if a number A is non-prime, you only need check whether there is a prime number <= sqrt(A) which divides A. (This would require you to keep a list of all primes already found, but should drastically improve the speed).
Or if you want to get hardcore, take a look at: http://primes.utm.edu/prove/index.html (The section titled 'Finding Very Small Primes' is closest to what you're trying to do)
|
|
| Back to top |
|
|
LeoDraco
Demon Hunter
Joined: 24 Jun 2003
Posts: 584
Location: Riverside, South Cali
|
| Posted: Tue Dec 05, 2006 6:10 pm Post subject: |
[quote] |
|
He does not appear to be declaring nor setting lp1, either, which confuses me.
Note: even with brute force methods, this is going to be extremely difficult to do. The search for primes is non-trivial; so non-trivial, that rather hefty awards are given for finding extremely huge prime numbers. Variations on the difficulty of factoring numbers and so forth are (at the most basic, handwaving level) the reasons why certain variants of public key cryptography are mostly secure.
In any case, there appear to be some interesting algorithms here.
_________________
"...LeoDraco is a pompus git..." -- Mandrake
|
|
| Back to top |
|
|
RedSlash
Mage
Joined: 12 May 2005
Posts: 331
|
| Posted: Wed Dec 06, 2006 1:06 am Post subject: |
[quote] |
|
|
A number is not prime if it is divisible by any prime number that is < square root of itself.
|
|
| Back to top |
|
|
cowgod
Wandering Minstrel
Joined: 22 Nov 2005
Posts: 114
Location: Pittsburgh, USA
|
| Posted: Wed Dec 06, 2006 7:04 pm Post subject: |
[quote] |
|
First of all, all primes are odd except for the number 2. Hardcode the 2, and then only check odd numbers.
Even better, hard code 2 and 3 and then observe that every other prime is of the form 6n + 1 or 6n + 5 (6n + 2 is divisible by 2, 6n + 3 is divisible by 3, etc.). Then you add 6 in each iteration of the loop and only check those 2 numbers.
You can do the same thing by hard coding 2, 3, and 5 and then working with 30n + whatever. I once wrote a program that stores the found all the primes that are relatively prime to p[0]p[1]...p[x] and between p[0]p[1]...p[x] and p[0]p[1]...p[x + 1]. It would then use those primes for another iteration with x + 1. This required eliminating multiples of p[x] with each iteration.
At the end, I would eliminate all the other non-primes, which were all multiples of the primes from the previous iteration.
So far as I know, it wasn't especially fast, and you run out of memory before long (even when storing only a single bit for each potential prime in the array).
|
|
| Back to top |
|
|
Rainer Deyke
Demon Hunter
Joined: 05 Jun 2002
Posts: 672
|
| Posted: Wed Dec 06, 2006 9:52 pm Post subject: |
[quote] |
|
Fastest/simplest way to find all primes up to a maximum:- create an array of bits, with size equal to the maximum. 'True' at any position means that the number is prime, 'false' means that it is not. Initialize to 'true' (i.e. mark all numbers as prime).
- Starting with position 2, iterate through the array.
- When you find a prime (i.e. the array value is 'true'), mark all multiples of that prime as non-prime (i.e. set their array value to 'false') before proceeding to the next value.
In Python that would be: | Code: | maximum = 1000000 # Or some other value
values = [True] * maximum
for i in range(2, maximum):
if values[i]:
print i
for j in range(i * 2, maximum, i):
values[j] = False |
Trivial to code. No multiplication. No division. O(n m) complexity, where n is the maximum and m is the actual number of primes. The only problem is memory consumption (bits equal to the maximum), which makes it impractical for truly large maximums (larger than 10 billion or so). And yes, it can be optimized in all kinds of ways, its runs fast enough that further optimizations are almost always unnecessary.
|
|
| Back to top |
|
|
Unknown
Moira's Silly Little Slave Bitch
Joined: 19 Jul 2005
Posts: 82
Location: Behind you...
|
| Posted: Fri Dec 08, 2006 3:50 pm Post subject: |
[quote] |
|
WOW!!! ok, well... this stupid phpBB posting parser won't let me post the code like it is.... if anyone is interested in the code click here to download it ---> http://www.shadowland.cc/primes.cpp
Ohh and the source code will explain where lp1 is "created"....
_________________
Most people would succeed in small things if they were not troubled with such great ambitions.
|
|
| Back to top |
|
|
DeveloperX
202192397
Joined: 04 May 2003
Posts: 1626
Location: Decatur, IL, USA
|
| Posted: Wed Dec 13, 2006 7:46 am Post subject: |
[quote] |
|
| Unknown wrote: | | this stupid phpBB posting parser won't let me post the code like it is.... |
| Code: |
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int MaxAmount = 0;
bool prime = true;
int main(){
ofstream PNS ("PrimeNumbers.dat");
cout << "Please give me a max number to get the primes up to: " << endl;
cin >> MaxAmount;
for(int lp=2;lp<MaxAmount;lp++){
if(lp % 2 !=1){lp++;}
for(int lp1=lp-1;lp1>1;lp1--){
if(lp % lp1 == 0){
prime = false;
}
}
if(prime){
PNS << lp << "\n";
}
prime = true;
}
PNS.close();
return 0;
}
|
looks like it posts code just fine Jeff. ;)
okay, heres mine :D
| Code: |
#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
bool numberIsPrime (int number)
{
if ( (2 > number) || (0 == number % 2) )
return false;
else if (2 == number)
return true;
int div = 3;
int lim = int(sqrt(number) + 1);
while (lim > div)
{
if (0 == number % div)
return false;
div += 2;
}
return true;
}
int main ()
{
ofstream PrimeFile ("primes.txt");
if (!PrimeFile)
{
cout << "Cannot create primes.txt!\n";
exit(1);
}
int maximum = 0;
cout << "Enter a number to calculate primes up to: ";
cin >> maximum;
for (int n = 1; n <= maximum; n++)
{
if (numberIsPrime (n))
{
if (PrimeFile)
{
PrimeFile << n << "\n";
}
}
}
if (PrimeFile)
PrimeFile.close ();
return 0;
}
|
_________________
Principal Software Architect
Rambling Indie Games, LLC
See my professional portfolio
|
|
| Back to top |
|
|
Unknown
Moira's Silly Little Slave Bitch
Joined: 19 Jul 2005
Posts: 82
Location: Behind you...
|
| Posted: Wed Dec 13, 2006 4:24 pm Post subject: |
[quote] |
|
NICE!!!
_________________
Most people would succeed in small things if they were not troubled with such great ambitions.
|
|
| Back to top |
|
|
tcaudilllg
Dragonmaster
Joined: 20 Jun 2002
Posts: 1731
Location: Cedar Bluff, VA
|
| Posted: Fri Dec 15, 2006 8:14 pm Post subject: |
[quote] |
|
|
I don't understand the focus on finding primes. Can someone explain it to me?
|
|
| Back to top |
|
|
Nodtveidt
Demon Hunter
Joined: 11 Nov 2002
Posts: 786
Location: Camuy, PR
|
| Posted: Fri Dec 15, 2006 11:13 pm Post subject: |
[quote] |
|
I usually equate it to SPS.
_________________
If you play a Microsoft CD backwards you can hear demonic voices. The scary part is that if you play it forwards it installs Windows. - wallace
|
|
| Back to top |
|
|
LeoDraco
Demon Hunter
Joined: 24 Jun 2003
Posts: 584
Location: Riverside, South Cali
|
| Posted: Sat Dec 16, 2006 8:06 am Post subject: |
[quote] |
|
| nodtveidt wrote: | | I usually equate it to SPS. |
Hurray for overloaded acronyms! As I am too tired/lazy to savvy which phrase you are using, care to explicate?
_________________
"...LeoDraco is a pompus git..." -- Mandrake
|
|
| Back to top |
|
|
Nodtveidt
Demon Hunter
Joined: 11 Nov 2002
Posts: 786
Location: Camuy, PR
|
| Posted: Sat Dec 16, 2006 2:18 pm Post subject: |
[quote] |
|
Actually, it isn't listed on wikipedia. SPS in this case refers to "small penis syndrome". :O
_________________
If you play a Microsoft CD backwards you can hear demonic voices. The scary part is that if you play it forwards it installs Windows. - wallace
|
|
| Back to top |
|
|
Unknown
Moira's Silly Little Slave Bitch
Joined: 19 Jul 2005
Posts: 82
Location: Behind you...
|
| Posted: Sat Dec 16, 2006 4:12 pm Post subject: |
[quote] |
|
small penis syndrome... hmm, is that something YOU are familiar with??? lets stay on topic shall we!
P.S. LG....here's some reading material http://www.rsasecurity.com/rsalabs/node.asp?id=2189
_________________
Most people would succeed in small things if they were not troubled with such great ambitions.
|
|
| Back to top |
|
|
