prime number

[sadjad]

hello everyone
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.

/**************************   


    * 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;   

}

please guide me.

[Roxoff]

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.

[Rubberman]

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 mid-1980'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 plain-text 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 dog-eared!

[drl]

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 storage-intensive, 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 encyclopedia