Results 1 to 4 of 4
Thread: prime number

Enjoy an ad free experience by logging in. Not a member yet? Register.



02022012 #1
 Join Date
 Feb 2012
 Posts
 1
prime number
I want to find the prime numbers between 20 thousand to 30 thousand of the following methods
۱ Single process
2 with 4 process
3 4 thread
4 10 thread
then I print runtime every programs.
Code:/************************** * prime_number.c * o + # * o + # * o + # * o + # * o + # * o + # * / /* algorithm : exclude all even numbers and * test all dividers up to the square root * exit loop when first divider is found */ #include <stdio.h> #include <math.h> int main (void) { int i, nb, count, test,limit; test = count = 0; for(nb=20000 ; nb<30000 ;nb++){ /* printf ("Enter integer: "); if (scanf ("%d", &nb) != 1) return 1; */ limit = sqrt(nb) + 1; if (nb % 2 == 0) test = 1; else{ for (i = 3 ; i < limit && ! test; i+=2, count++) if (nb % i == 0) test = 1; } if (!test) printf ("%d prime number, number of iterations = %dn", nb, count); /* else printf ("%d not prime number, number of iterations = %dn", nb, count); */ } return 0; }

02022012 #2
Hmm  looks like a homework question to me. At least you have a start...
You need to be able to launch a thread. I'd do it like this:
Have a global (and resource locked by some sort of semaphore or spinlock) method that doles out the 'next' number in the cycle.
Build an array of thread pointers that contain the code you posted, but instead of doing it in fixed loop, have it call the global resource for the 'next' number and either process it using your algorthim, or quit if there are no more numbers left.Linux user #126863  see http://linuxcounter.net/

02052012 #3
 Join Date
 Apr 2009
 Location
 I can be found either 40 miles west of Chicago, in Chicago, or in a galaxy far, far away.
 Posts
 14,009
Definitely a homework assignment. I assume you are using the Sieve of Eratosthenes. The algorithm is really quite straightforward. The interesting part of the assignment is how to partition the problem so you can use multiple threads/processes to speed it up. The last time I actually implemented this stuff was back in the mid1980's in order to break large numbers into their prime factors (RSA public key encryption), and generate Goedel numbers from strings of text, and restore the plaintext from the Goedel numbers, which requires the same techniques to break big numbers into prime factors. If you are interested, there is a reasonable treatment of Goedel Numbers in the Wikipedia, but if you want to know how to apply that to strings of text, then you might want to check out of the library (a good university library) the "VNR Concise Encyclopedia of Mathematics", which has a good section of this stuff. My copy (almost 30 years old now) is getting rather dogeared!
Sometimes, real fast is almost as good as real time.
Just remember, Semper Gumbi  always be flexible!

02052012 #4
 Join Date
 Apr 2006
 Location
 Saint Paul, MN, USA / CentOS, Debian, Slackware, {Free, Open, Net}BSD, Solaris
 Posts
 1,455
Hi.
The code looks like trial division, not a sieve.
The sequence is fairly small, ~ 10000 numbers, so my take is that there will not be much difference in timings for thread counts. However, if the code runs correctly for a short sequence, then it could be timed for something on which it can chew for a while.
I think I see what Roxoff is suggesting. I'd be inclined to think that a sieve would be more storageintensive, but generally more efficient. I tend to avoid division where I can, but using trial division seems like an easier programming task.
The last time I did something similar was (also) many years ago. I seem to recall using the abstraction of a long bit string to save storage (64K on a CDC 6600, I think), each bit position representing an odd integer. I ran a sieve on that, saving the (binary) array for future runs  like saving a Fibonacci sequence once one has it available.
If one had the time, a comparison of the runs of the algorithms would be interesting.
Bests wishes ... cheers, drl
Sieve of Eratosthenes  Wikipedia, the free encyclopediaWelcome  get the most out of the forum by reading forum basics and guidelines: click here.
90% of questions can be answered by using man pages, Quick Search, Advanced Search, Google search, Wikipedia.
We look forward to helping you with the challenge of the other 10%.
( Mn, 2.6.n, AMD64 3000+, ASUS A8V Deluxe, 1 GB, SATA + IDE, Matrox G400 AGP )