Question

Prime Number Programing in C

Note: The program is to be written using the bitwise operation. Use an integer array (not a Boolean array) and a bit length (for instance 32 bits).

In this program you will write a C program to find all prime numbers less than 10,000. You should use 10,000 bits to correspond to the 10,000 integers under test. You should initially turn all bits on (off) and when a number is found that is not prime, you should turn the corresponding bit off (on). Completion of the program requires going through all bits and printing the decimal numbers corresponding to those bits that remain on (off).

You should use the Sieve of Eratosthenes algorithm to find all the primes. The algorithm will be

discussed in class. You should investigate some efficiency steps to improve the performance of the algorithm to be measured in the number of comparisons and byte assignments that you use. For example, consider how you might make use of the fact that all even numbers after 2 will not be prime or how to reduce the number of comparisons and assignments when marking off multiples of higher primes.

After finding all primes, you should print the prime numbers out as decimal (base 10) numbers.

There may be a large number of prime numbers less than 10,000. To minimize the output, you should print the first 500 primes so that there are 5-10 prime numbers per line. You should then print a summary line of the total number of prime numbers that you found less than 10,000.

To provide a sense of how efficient your program is, you should output a count of the number of

comparisons and the number of assignments that your program has performed. This will be discussed further in class.

Be sure to submit an analysis of the results of your program. The analysis should include the number of comparisons and the number of assignments as a summary of the output from your program and some verification that the results are correct.

The program should be written to be as efficient as possible.

You should call printf with a decimal format (%d) to print a number. If you use a format of the form %7d as an example, it will print the number in a field width of 7. That is very convenient for printing the numbers in columns.

I need to rewrite this program as stated below. The program needs to be written as follows: 1. USE an integer array (ex: int mask[NUM] - NOT A BOOLEAN ARRAY(not bool mask[NUM]. 2. USE a bitwise operation for the length of the bit. (ex. bitLength 32) to specify how the number would be stored in memory.

Not like the initial version of what I have written below:

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

int main ()

{

            int NUM = 10000;

            bool mask[NUM];

            int count=0;

            int lineCount=0;

            int numberOfComparison = 0;

            int numberOfAssignment = 0;

            int totalComputation = 0;

            //Initially masking all numbers as prime.

            for(int i=0; i<NUM; i++)

                        mask[i] = true;

            //This loop mask non-prime number.

            for(int p = 2; p <=NUM; p++)

            {

                        if(mask[p])

                        {

                                    numberOfComparison++;

                                    for(int j=p*2; j<=NUM; j=j+p)

                                                {mask[j] = false;

                                                numberOfAssignment++;

                                                }

                        }

            }

           

            //Print prime numbers.

            printf("\n First 500 Prime Numbers: \n");

            for(int i=2; i<NUM; i++)

                        {

                                    if(mask[i])

                                    {

                                                if (count < 500)

                                                            printf("%7d", i);

                                                count++;

                                                lineCount++;

                                    }

                                    if((lineCount > 0 && count < 500) && (lineCount %10==0))

                                    {

                                                printf("\n");

                                                lineCount=0;

                                    }

                        }

           

            //Prints program results:

            printf("\n\n

            printf("\n prime numbers less than 10,000: %d \n", count);

            printf("\n comparison are: %d \n", numberOfComparison);

            printf("\n Assignments are: %d \n\n", numberOfAssignment);

           

            return (0);

}

Answer 1

/* *Program name: primeNumber.c

* This is a C program that finds all prime numbers less than 10,000 using Sieve of Eratosthenes algorithm.

* The first five hundred prime numbers that are found are displayed using decimal (base 10) numbers.

*/

#include <stdio.h>

#include <stdlib.h>

int main()

{

int NUM = 10000;

int mask[NUM];

int count = 0;

int lineCount = 0;

int numberOfComparison = 0;

int numberOfAssignment = 0;

int totalComputation = 0;

//Initially masking all numbers as prime.

for (int i = 0; i < NUM; i++)

mask[i] = 1;

//This loop mask non-prime number.

for (int p = 2; p <= NUM; p++)

{

if (mask[p])

{

numberOfComparison++;

for (int j = p * 2; j <= NUM; j = j + p)

{

mask[j] = 0;

numberOfAssignment++;

}

}

}

printf("\n Hello dear user. This program computes prime numbers less than 10,000. "

"\n But only the first five hundred prime numbers are printed for your convenient.\n");

//Print prime numbers.

printf("\n First 500 Prime Numbers: \n");

for (int i = 2; i < NUM && count < 500; i++)

{

if (mask[i])

{

printf("%7d", i);

count++;

if (count % 10 == 0)

printf("\n");

}

}

totalComputation = numberOfComparison + numberOfAssignment;

//Prints program results:

printf("\n\n ********************************************************************** \n **********************************************************************\n");

printf("\n The total prime numbers less than 10,000: %d \n", count);

printf("\n The number of comparison are: %d \n", numberOfComparison);

printf("\n The number of Assignments are: %d \n\n", numberOfAssignment);

printf("===== Total number of computation =====: %d\n", totalComputation);

return (0);

}

I have one doubt, why and where we need to use bitwise operations? I will definitely give solution, I am in little bit confuction...