Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old May 16th, 2005, 12:49 PM   #1
thomzor
Newbie
 
Join Date: Apr 2005
Location: The Netherlands
Posts: 20
Rep Power: 0 thomzor is on a distinguished road
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
thomzor is offline   Reply With Quote
Old May 16th, 2005, 2:38 PM   #2
Nuticulus
Programmer
 
Nuticulus's Avatar
 
Join Date: May 2005
Location: England
Posts: 61
Rep Power: 4 Nuticulus is on a distinguished road
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);
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.

Last edited by Nuticulus; May 17th, 2005 at 1:26 AM.
Nuticulus is offline   Reply With Quote
Old May 16th, 2005, 5:28 PM   #3
brkstf
Programmer
 
brkstf's Avatar
 
Join Date: Feb 2005
Posts: 89
Rep Power: 4 brkstf is on a distinguished road
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.
brkstf is offline   Reply With Quote
Old May 17th, 2005, 1:03 AM   #4
thomzor
Newbie
 
Join Date: Apr 2005
Location: The Netherlands
Posts: 20
Rep Power: 0 thomzor is on a distinguished road
@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
thomzor is offline   Reply With Quote
Old May 17th, 2005, 1:53 AM   #5
Nuticulus
Programmer
 
Nuticulus's Avatar
 
Join Date: May 2005
Location: England
Posts: 61
Rep Power: 4 Nuticulus is on a distinguished road
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.
Nuticulus is offline   Reply With Quote
Old May 17th, 2005, 5:43 AM   #6
thomzor
Newbie
 
Join Date: Apr 2005
Location: The Netherlands
Posts: 20
Rep Power: 0 thomzor is on a distinguished road
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 is offline   Reply With Quote
Old May 17th, 2005, 10:31 AM   #7
Ooble
I eat cake for breakfast.
 
Ooble's Avatar
 
Join Date: Jul 2004
Location: In my box.
Posts: 4,434
Rep Power: 9 Ooble is on a distinguished road
Quote:
Originally Posted by Nuticulus
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.
Actually, because you're multiplying two numbers, you only need to go up to the square root of the number. Make sure you test the square root though, otherwise 4, for example, will be found to be a prime.

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;
}
__________________
Me :: You :: Them

Last edited by Ooble; May 17th, 2005 at 10:41 AM.
Ooble is offline   Reply With Quote
Old May 17th, 2005, 11:19 AM   #8
thomzor
Newbie
 
Join Date: Apr 2005
Location: The Netherlands
Posts: 20
Rep Power: 0 thomzor is on a distinguished road
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
thomzor is offline   Reply With Quote
Old May 17th, 2005, 2:13 AM   #9
LOI Kratong
Professional Programmer
 
Join Date: May 2005
Location: Woo - Boot Sector!
Posts: 294
Rep Power: 4 LOI Kratong is on a distinguished road
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
LOI Kratong is offline   Reply With Quote
Old May 17th, 2005, 7:51 AM   #10
thomzor
Newbie
 
Join Date: Apr 2005
Location: The Netherlands
Posts: 20
Rep Power: 0 thomzor is on a distinguished road
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 is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

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

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 4:13 PM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC