![]() |
|
![]() |
|
|
Thread Tools | Display Modes |
|
|
|
|
#1 |
|
Newbie
Join Date: Apr 2005
Location: The Netherlands
Posts: 20
Rep Power: 0
![]() |
Prime numbers
ok basically i created a program to calculate the primes from 0 to a given number up to about 500.000 (not sure)
please give me your opinions about it and perhaps stuff i can improve #include <iostream>
#include <cstdlib>
#include <windows.h>
using namespace std;
void c_primes(long param);
void c_primes(long param)
{
float t_before, t_after;
long int arr_primes[param],i,j;
for (i=2;i<=param;i++)
{
arr_primes[i]=i;
}
t_before=GetTickCount();
for (i=2;i<=param;i++)
{
if (arr_primes[i] == 0) { continue; }
for (j=(i+1);j<=param;j++)
{
if (arr_primes[j] != 0 && arr_primes[j]%i==0)
{
arr_primes[j]=0;
}
}
}
t_after=GetTickCount();
cout<<"\n\nCalculation time: "<<t_after-t_before<<" milliseconds\n\n";
cout<<"Press a key to display the prime numbers\n";
system("PAUSE");
cout<<"\nPrimes from 0 to "<<param<<":\n";
for (long x=2;x<param+1;x++)
{
if (arr_primes[x] != 0) { cout<<arr_primes[x]<<", "; }
}
cout<<"\n";
delete [] arr_primes;
}
int main(int argc, char *argv[])
{
long m_primes;
cout<<"\n Welcome\n\Calculate prime numbers from 0 to: ";
cin>>m_primes;
c_primes(m_primes); //c_primes stands for calculate primes
system("PAUSE");
return EXIT_SUCCESS;
}basic explanation is, it loops through an array of numbers, when it's not a prime it sets the value to 0 (afterwards it prints them) ofcourse there are many more and also easier ways to do it but this works quite fine you can also output it all to a file by creating a .bat file (or just write a function which writes the stuff to disk) which contains @echo off nameoftheexe.exe >> nameofthetextfile.txt |
|
|
|
|
|
#2 |
|
Programmer
Join Date: May 2005
Location: England
Posts: 61
Rep Power: 4
![]() |
That's stupidly complex. Regard this code, which generates prime numbers infinitely:
#include <stdio.h>
int main(void)
{
int x=1,y;
while(x++)
{
for(y=2;x%y;)
printf(++y/x+"\0%d\n", x);
}
return 0;
}Now isn't that better? Edit: I should probably add, to avoid confusion, that this code isn't mine. In fact, it was a very succinct C one-liner that I once saw in someone's sig. I simply expanded it so that it looked a bit less obsfucated. The thing that makes me sit in most awe is this bit: printf(++y/x+"\0%d\n", x); On second thoughts, the lack of if() there doesn't save instructions. It makes for more. Nice way of cutting down on code, though. And I've tried thomzor's strategy, it really is better. Nice work. Although, when generating lots of numbers it'll be costly in terms of memory.
__________________
http://www.nuticulus.net/hackmysig/sig.PNG Give my site a chance, you know you want to ;-) Google will solve 99% of your problems. Including those with your sex life. Caution, may <strike>contain</strike> be nuts. Last edited by Nuticulus; May 17th, 2005 at 1:26 AM. |
|
|
|
|
|
#3 |
|
Programmer
Join Date: Feb 2005
Posts: 89
Rep Power: 4
![]() |
the elegance of saving an instruction is quickly overshadowed by the bad algorithm. somewhere around the 4td or 5th prime number found, thomzor's strategy will be better than yours in terms of milliseconds per prime number found.
|
|
|
|
|
|
#4 |
|
Newbie
Join Date: Apr 2005
Location: The Netherlands
Posts: 20
Rep Power: 0
![]() |
@Nuticulus
short code isn't always better : / i mean, it's neat - ofcourse. but it can be hard to read for someone else and perhaps it isn't not even as good as it looks anyways thanks for the feedback |
|
|
|
|
|
#5 |
|
Programmer
Join Date: May 2005
Location: England
Posts: 61
Rep Power: 4
![]() |
I've cogitated on this for a little bit, and figured I might share some ideas about this.
Firstly, all primes, with the exception of 2, are odd numbers. So at the beginning of your array initialisation, you pretty much need only to place odd numbers into your array. Or at least, you only need to test the odd numbers from your array. Secondly, since all the numbers in the array are odd numbers, none of them will be divisible by an even number. So you can remove all the even numbers from your testing. Thirdly, (and this one's common sense), you only need to test half the numbers up to the value of the tested number. I.e, you know that x will not be cleanly divisible by a number that's greater than x/2, apart from x.
__________________
http://www.nuticulus.net/hackmysig/sig.PNG Give my site a chance, you know you want to ;-) Google will solve 99% of your problems. Including those with your sex life. Caution, may <strike>contain</strike> be nuts. |
|
|
|
|
|
#6 | |
|
Newbie
Join Date: Apr 2005
Location: The Netherlands
Posts: 20
Rep Power: 0
![]() |
Quote:
i'll try it after shcool today ![]() |
|
|
|
|
|
|
#7 | |
|
I eat cake for breakfast.
![]() ![]() ![]() ![]() Join Date: Jul 2004
Location: In my box.
Posts: 4,434
Rep Power: 9
![]() |
Quote:
Here's a program I wrote a while back when I was bored: #include <stdio.h>
#include <math.h>
#define true 1
#define false 0
int is_prime (double num)
{
long i;
if (num < 2)
{
return false;
}
else if (num == 2)
{
return true;
}
else
{
for (i = 3; i <= sqrt(num); i += 2)
{
if ((num / i) == ceil(num / i))
{
return false;
}
}
return true;
}
}
int main ()
{
double i;
for (i = 1; i > 0; i++)
{
if (is_prime(i))
{
printf("%.0f\n", i);
}
}
getchar();
return 0;
}Last edited by Ooble; May 17th, 2005 at 10:41 AM. |
|
|
|
|
|
|
#8 |
|
Newbie
Join Date: Apr 2005
Location: The Netherlands
Posts: 20
Rep Power: 0
![]() |
unsigned long prime_array[prime_count];
change that line ^ into the one below (in my program) unsigned long * prime_array = new unsigned long [prime_count]; with the 1st line u cant even calculate 2mil, now u can go as far as 4294967295(if im correct) 4 bytes that is i estimate 10 mil will take about 30 minutes (quite alot eh, on a p4 2,4ghz that is) :p @Ooble thanks for the tip regarding the sqrt, the speed will increase at higher numbers perhaps, but a sqrt is quite a few clock ticks so not all that usefull at lower #'s (i think, not sure) i'll try it out anyway :p |
|
|
|
|
|
#9 |
|
Professional Programmer
Join Date: May 2005
Location: Woo - Boot Sector!
Posts: 294
Rep Power: 4
![]() |
Looks good, there are so many ways of finding primes that it's stupid to say mine's the best. They're both cool :p
__________________
www.heldtogether.co.uk |
|
|
|
|
|
#10 |
|
Newbie
Join Date: Apr 2005
Location: The Netherlands
Posts: 20
Rep Power: 0
![]() |
Thirdly, (and this one's common sense), you only need to test half the numbers up to the value of the tested number. I.e, you know that x will not be cleanly divisible by a number that's greater than x/2, apart from x.
did that in my previous program, that must be why this one is 4 seconds slower on the 100000 -.- :p this one takes about 7 seconds, my previous one did it in 3,5 but deleted it thanks for pointing that out im also working on the one w/ only odd numbers cya |
|
|
|
![]() |
| Bookmarks |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
| Thread Tools | |
| Display Modes | |
|
|