# Prime Numbers

Page 1 of 1

## 1 Replies - 2099 Views - Last Post: 24 January 2012 - 02:45 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=364191&amp;s=2ab5b08afc3192be24f47fa309dd74fc&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 browngod2002

Reputation: 4
• 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>

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

/* Function main begins program execution */
int main(void)
{
unsigned int i;
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

Reputation: 454
• 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.