Programming Forums > Application Development > C++

thomzor · May 16th, 2005, 12:49 PM

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

(Toggle Plain Text)

#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

Nuticulus · May 16th, 2005, 2:38 PM

That's stupidly complex. Regard this code, which generates prime numbers infinitely:

(Toggle Plain Text)

#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:

(Toggle Plain Text)

printf(++y/x+"\0%d\n", x);

That's such an elegant solution to removing an if statement (gets rid of a CMP instruction, at least), that it makes me want to explode in my pants. Ohh, if only everyone coded as elegantly as that.

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.

brkstf · May 16th, 2005, 5:28 PM

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.

thomzor · May 17th, 2005, 1:03 AM

@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

Nuticulus · May 17th, 2005, 1:53 AM

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.

LOI Kratong · May 17th, 2005, 2:13 AM

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

thomzor · May 17th, 2005, 5:43 AM

Quote:

Originally Posted by Nuticulus

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.

ur making a point though about only putting odd's in the array, saves memory and all

i'll try it after shcool today

thomzor · May 17th, 2005, 7:51 AM

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

thomzor · May 17th, 2005, 9:48 AM

Ok I came up with a solution, here is it;

[PHP]#include <iostream>
#include <windows.h>

using namespace std;

int main(int argc, char *argv[])
{
//Setup variables
float starttime, endtime;
unsigned long prime_count, i, j;
if (atoi(argv[1])%2==0)
{
prime_count=atoi(argv[1])/2;
} else {
prime_count=(atoi(argv[1])+1)/2;
}
unsigned long prime_array[prime_count];

//Setup the array of numbers
prime_array[0]=2;
prime_array[1]=3;
starttime=GetTickCount();
for (i=2;i<prime_count;i++)
{
prime_array[i]=prime_array[i-1]+2;
}

//Calculate the primes
for (i=1;i<prime_count;i++)
{
for (j=1;j<i;j++)
{
if (prime_array[j]==0)
{
continue;
} else if (prime_array[i]%prime_array[j]==0) {
prime_array[i]=0;
break;
}
}
}
endtime=GetTickCount();

//Output
cout<<"Calculation time: "<<endtime-starttime<<" milliseconds\n\nPrimes:\n";
for (i=0;i<prime_count;i++)
{
if (prime_array[i]!=0) { cout<<prime_array[i]<<", "; }
}
}[/PHP]

i know there are some crappy parts init, please give me some feedback and better solutions on them to optimize the whole

this one takes only 3 seconds on 0->100.000

which is half the time it took the past algo, props for nuticulus also

Calculation time: 3072 milliseconds

Primes:
2, 3, 5, 7, 11... etc

(and again the batch file code (.bat))
@echo off
del prime.txt
prime.exe 100000 >> prime.txt

Nuticulus · May 17th, 2005, 10:07 AM

Just came home from school. Had my first written GCSE exam of the year -- Latin.

Anyway, if you're only doubling your performance, you're not doing enough of the things I recommend. The things I mentioned should at least quadruple speed, if not octuple. Also, to avoid using up tons of memory, I recommend you work in "batches". By this I mean:

*Attempting to test numbers up to 100,000*
*Create array of ints 1000 items long*
*Assign numbers 1-1000 to array*
*Test and output*
*Assign numbers 1001-2000 to array*
*Test and output*
And so on. This should cut down on memory usage quite a bit.

Optimise your compiler options. That should reduce some of the bloatiness in there.

May 16th, 2005, 12:49 PM	#1
thomzor 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 (Toggle Plain Text) #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; } #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

May 16th, 2005, 2:38 PM	#2
Nuticulus Programmer Join Date: May 2005 Location: England Posts: 61 Rep Power: 4	That's stupidly complex. Regard this code, which generates prime numbers infinitely: (Toggle Plain Text) #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; } #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: (Toggle Plain Text) printf(++y/x+"\0%d\n", x); printf(++y/x+"\0%d\n", x); That's such an elegant solution to removing an if statement (gets rid of a CMP instruction, at least), that it makes me want to explode in my pants. Ohh, if only everyone coded as elegantly as that. 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.

May 17th, 2005, 1:53 AM	#5
Nuticulus 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.

May 17th, 2005, 2:13 AM	#6
LOI Kratong 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

May 17th, 2005, 10:07 AM	#10
Nuticulus Programmer Join Date: May 2005 Location: England Posts: 61 Rep Power: 4	Just came home from school. Had my first written GCSE exam of the year -- Latin. Anyway, if you're only doubling your performance, you're not doing enough of the things I recommend. The things I mentioned should at least quadruple speed, if not octuple. Also, to avoid using up tons of memory, I recommend you work in "batches". By this I mean: Attempting to test numbers up to 100,000 Create array of ints 1000 items long Assign numbers 1-1000 to array Test and output Assign numbers 1001-2000 to array Test and output And so on. This should cut down on memory usage quite a bit. Optimise your compiler options. That should reduce some of the bloatiness in there. __________________ 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.

May 16th, 2005, 5:28 PM	#3
brkstf 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.

May 17th, 2005, 1:03 AM	#4
thomzor 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

May 17th, 2005, 7:51 AM	#8
thomzor 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

May 17th, 2005, 9:48 AM	#9
thomzor Newbie Join Date: Apr 2005 Location: The Netherlands Posts: 20 Rep Power: 0	Ok I came up with a solution, here is it; [PHP]#include <iostream> #include <windows.h> using namespace std; int main(int argc, char *argv[]) { //Setup variables float starttime, endtime; unsigned long prime_count, i, j; if (atoi(argv[1])%2==0) { prime_count=atoi(argv[1])/2; } else { prime_count=(atoi(argv[1])+1)/2; } unsigned long prime_array[prime_count]; //Setup the array of numbers prime_array[0]=2; prime_array[1]=3; starttime=GetTickCount(); for (i=2;i<prime_count;i++) { prime_array[i]=prime_array[i-1]+2; } //Calculate the primes for (i=1;i<prime_count;i++) { for (j=1;j<i;j++) { if (prime_array[j]==0) { continue; } else if (prime_array[i]%prime_array[j]==0) { prime_array[i]=0; break; } } } endtime=GetTickCount(); //Output cout<<"Calculation time: "<<endtime-starttime<<" milliseconds\n\nPrimes:\n"; for (i=0;i<prime_count;i++) { if (prime_array[i]!=0) { cout<<prime_array[i]<<", "; } } }[/PHP] i know there are some crappy parts init, please give me some feedback and better solutions on them to optimize the whole this one takes only 3 seconds on 0->100.000 which is half the time it took the past algo, props for nuticulus also Calculation time: 3072 milliseconds Primes: 2, 3, 5, 7, 11... etc (and again the batch file code (.bat)) @echo off del prime.txt prime.exe 100000 >> prime.txt

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Application Development > C++

Prime numbers