Fedora Linux Support Community & Resources Center
  #1  
Old 3rd September 2011, 06:08 PM
renkinjutsu Offline
Registered User
 
Join Date: Mar 2010
Posts: 87
linuxchrome
Program to find prime numbers

I found this site "Project Euler" that has many programming challenges. link.

I just started taking a CS class and found programming to be fun, so I tried my hand at some of these problems..

I have made a prime number generator for some of the easier problems, but they were rather inefficient because it divides every odd number by half of the odd numbers below it... So the more it calculates, the slower it becomes.. The problem I'm on requires me to calculate prime numbers up to 2 million.

So I decided to edit the algorithm a bit so that it divides every odd number by previous prime numbers, but it stops as soon as it calculates 3 prime numbers.

Can anyone see why my program stops running after just a bit?


Code:
#include<stdio.h>
main(void) {
	
	int number, prime, i, j;
	// max defines the upper-bound. 
	// Example: find all prime numbers between 1-900000
	int max = 900000;
	// amount defines the amount of prime numbers to calculate
	// Example: Calculate 10001 prime numbers
	int amount = 10001;
	int primes[] = {2,3,5,7};

	j = 3;

	printf("2\n");
	for(number = 7; number < max && j < amount; number = number + 2) {

		prime = 1;
		for(i = 0; i <= j; i++) {
			if(number % primes[i] == 0)
				prime = 0;
		}
		if(prime) {
			printf("%d\n", number);
			j++;
			primes[j] = number;
		}
	}
}
Reply With Quote
  #2  
Old 3rd September 2011, 10:40 PM
giulix Offline
Registered
 
Join Date: Oct 2005
Location: CE(S)T
Posts: 3,242
linuxfirefox
Re: Program to find prime numbers

You defined primes to be an array of 4 elements on the stack, so its size if fixed to 4. Store the array elements dynamically in the heap or initialize the array to 2M elements
__________________
Asus K55VD, i5 3230M - Productivity/Programming (F24)
Asus M32CD - i7-6700, Asus STRIX-GTX970-DC2OC-4GD, 1x8 GB Sk Hynix 2133 MHz DDR4 - Gaming (W10)
HP Proliant DL 360 G5 - Heavy lifting (CentOS 7.2)
Reply With Quote
  #3  
Old 3rd September 2011, 10:50 PM
renkinjutsu Offline
Registered User
 
Join Date: Mar 2010
Posts: 87
linuxchrome
Re: Program to find prime numbers

The program worked in a small scale, so I thought it was fine.
It found at least 3 prime numbers and stored them in the array. I still have much learning to do.
Reply With Quote
  #4  
Old 3rd September 2011, 10:55 PM
giulix Offline
Registered
 
Join Date: Oct 2005
Location: CE(S)T
Posts: 3,242
linuxfirefox
Re: Program to find prime numbers

I never got a program right the first time. You could initialize the array to 2M elements (fixed) like this:
Code:
#define ARRAY_SIZE 2000000
...
int primes[ARRAY_SIZE];
__________________
Asus K55VD, i5 3230M - Productivity/Programming (F24)
Asus M32CD - i7-6700, Asus STRIX-GTX970-DC2OC-4GD, 1x8 GB Sk Hynix 2133 MHz DDR4 - Gaming (W10)
HP Proliant DL 360 G5 - Heavy lifting (CentOS 7.2)

Last edited by giulix; 3rd September 2011 at 10:59 PM. Reason: I didn't even get these 2 lines right the first time: I missed the semicolon :D
Reply With Quote
  #5  
Old 3rd September 2011, 11:06 PM
renkinjutsu Offline
Registered User
 
Join Date: Mar 2010
Posts: 87
linuxchrome
Re: Program to find prime numbers

Thanks for the advice.. Just curious though. Is there a way to dynamically grow the array?
Reply With Quote
  #6  
Old 4th September 2011, 01:08 AM
giulix Offline
Registered
 
Join Date: Oct 2005
Location: CE(S)T
Posts: 3,242
linuxfirefox
Re: Program to find prime numbers

Yes, but you have to use one of calloc(), malloc() or realloc()
__________________
Asus K55VD, i5 3230M - Productivity/Programming (F24)
Asus M32CD - i7-6700, Asus STRIX-GTX970-DC2OC-4GD, 1x8 GB Sk Hynix 2133 MHz DDR4 - Gaming (W10)
HP Proliant DL 360 G5 - Heavy lifting (CentOS 7.2)
Reply With Quote
  #7  
Old 4th September 2011, 01:29 AM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,479
linuxfedorafirefox
Re: Program to find prime numbers

I normally avoid Perl, but in this case it's a good fit:
Code:
perl -e '$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/&&print"$_ "while ++$_'
It will keep finding primes until you interrupt it with Ctrl-c.
Reply With Quote
  #8  
Old 4th September 2011, 03:17 AM
stevea
Guest
 
Posts: n/a
linuxfedorafirefox
Re: Program to find prime numbers

Or for something a lot faster ....
sudo yum install pari-gp
gp
primes(10000)
Reply With Quote
  #9  
Old 4th September 2011, 05:04 AM
renkinjutsu Offline
Registered User
 
Join Date: Mar 2010
Posts: 87
linuxchrome
Re: Program to find prime numbers

Quote:
Originally Posted by RupertPupkin View Post
I normally avoid Perl, but in this case it's a good fit:
Code:
perl -e '$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/&&print"$_ "while ++$_'
It will keep finding primes until you interrupt it with Ctrl-c.
should I let this run overnight?
Reply With Quote
  #10  
Old 4th September 2011, 07:40 AM
RupertPupkin Offline
Registered User
 
Join Date: Nov 2006
Location: Detroit
Posts: 6,479
linuxfedorafirefox
Re: Program to find prime numbers

Quote:
Originally Posted by renkinjutsu View Post
should I let this run overnight?
Yes...yes you should.
Reply With Quote
Reply

Tags
numbers, prime, program

Thread Tools Search this Thread
Search this Thread:

Advanced Search
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

Similar Threads
Thread Thread Starter Forum Replies Last Post
I need to find a program. running_rabbit Using Fedora 2 9th November 2009 04:05 PM
Cannot find the autorun program SHAKEandBAKE Using Fedora 3 25th March 2009 05:50 PM
Where to find program documentation Doug G Using Fedora 6 26th August 2008 02:12 AM
A Skype-like program to be able to call regular telephone numbers, but For Free? beeball Using Fedora 3 24th January 2008 06:01 AM
Where to find newly installed program? chemphi Using Fedora 3 12th April 2004 09:41 PM


Current GMT-time: 07:42 (Saturday, 25-03-2017)

TopSubscribe to XML RSS for all Threads in all ForumsFedoraForumDotOrg Archive
logo

All trademarks, and forum posts in this site are property of their respective owner(s).
FedoraForum.org is privately owned and is not directly sponsored by the Fedora Project or Red Hat, Inc.

Privacy Policy | Term of Use | Posting Guidelines | Archive | Contact Us | Founding Members

Powered by vBulletin® Copyright ©2000 - 2012, vBulletin Solutions, Inc.

FedoraForum is Powered by RedHat