1 Replies - 2099 Views - Last Post: 24 January 2012 - 02:45 PM Rate Topic: -----

#1 browngod2002  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 27
  • Joined: 16-September 06

Prime Numbers

Posted 26 November 2006 - 07:13 AM

Description: using the sieve of erastosthenes algorithm to find the prime factors of 1000 integers starting from 2. 1 is not a prime factor.
/********************************************************************/
/* Title: P256N6.30                                                 */
/* Author: Matthew Schofield                                        */
/* Date: 10/24/2006                                                 */
/* Purpose: This program will display all the prime factors from    */
/*          1 to 1000. Using The Sieve of Eratosthenes algorithm.   */
/*                                                                  */
/*         Inputs: The input(s) are an array of 1000 elements       */
/*                 initialized to 2.                                */
/*         Output: All the prime numbers from 1 to 1000 with        */
/*                 the total number of prime integers calculated    */
/*                 and displayed.                                   */
/********************************************************************/

#include<stdio.h>

#define PRIMENUM 1000

/* Function prototype */
void Prime_Num(unsigned int num[]);

/* Function main begins program execution */
int main(void)
{
     unsigned int i;
     unsigned int num[PRIMENUM];
     unsigned int count = 0;
     

     for (i = 0; i < PRIMENUM; i++)/*Populates the array and then sets all elements*/
          num[i] = 2;               /*to 2*/

     Prime_Num(num);

        for(i = 0; i < PRIMENUM; i++) /*Loops through and prints all prime numbers */
     {                           /*Also counts the prime numbers that are displayed*/
                                   /*And prints both on the screen*/
          if(num[i]!=0)
            {
              printf("%dn",num[i]);
               count++;
            }
      }

    printf("There are a total of %d prime integers.n", count);
     getchar();
     getchar();
     
     return 0;
}/* end main */

/*Function void Prime_Num(int num[]) finds the prime integers */
void Prime_Num(unsigned int num[])
{
     unsigned int i;
     unsigned int j;     
     
     for(i = 1; i < PRIMENUM; i++)   /*loops through the array starting with array subscript 2*/
          num[i] = i + 1;         
          
     for(i = 0; i < PRIMENUM; i++) /*loops through to find the prime integers for the rest of the array*/
     {
          if(num[i]!=0)
          {
               for(j = i + 1; j < PRIMENUM; j++)
               {
                    if(num[j]!= 0)
                    {
                         if((num[j] % num[i])== 0)     /*check if num[j]*/ 
                         num[j] = 0;                    /*is a multiple of num[i]*/
                                                       /*if it is a multiple then set it to 0*/
                    }
               }
          }
     }
}/*end of Prime_Num */


Is This A Good Question/Topic? 0
  • +

Replies To: Prime Numbers

#2 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 454
  • View blog
  • Posts: 864
  • Joined: 17-March 11

Re: Prime Numbers

Posted 24 January 2012 - 02:45 PM

The algorithm to find primes, is not sieve of erastosthenes. Sieve steps through a list of numbers/bitset with step length of the last prime found and crosses out/removes those numbers. This algorithm takes steps of one and tries to divide the number.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1