Find the answer to your Linux question:
Results 1 to 4 of 4
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- ...
Enjoy an ad free experience by logging in. Not a member yet? Register.
  1. #1
    Just Joined!
    Join Date
    Feb 2012
    Posts
    1

    prime number


    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.

    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;   
    
    }
    please guide me.

  2. #2
    Super Moderator Roxoff's Avatar
    Join Date
    Aug 2005
    Location
    Nottingham, England
    Posts
    3,906
    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/

  3. #3
    Linux Guru Rubberman's Avatar
    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
    11,677
    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!
    Sometimes, real fast is almost as good as real time.
    Just remember, Semper Gumbi - always be flexible!

  4. $spacer_open
    $spacer_close
  5. #4
    drl
    drl is offline
    Linux Engineer drl's Avatar
    Join Date
    Apr 2006
    Location
    Saint Paul, MN, USA / CentOS, Debian, Slackware, {Free, Open, Net}BSD, Solaris
    Posts
    1,294
    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
    Welcome - 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, AMD-64 3000+, ASUS A8V Deluxe, 1 GB, SATA + IDE, Matrox G400 AGP )

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •