Question

A Prime number is an integer greater than 1 that cannot be formed by multiplying two smaller integer other than 1 and itself. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1. In this question you will write a program that takes a sequence of integers from the user and display all the prime numbers contained in that sequence. We will separate this question in 2 steps

Step 1 (5 pts) Write a script that accepts a sequence of positive integer from the user and display all the prime numbers from that sequence. Your program should accept and save in a list the input from the user until the value -1 is entered. Your program should also make sure that only positive values are entered. You can assume the users only enter integers.

Step 2 (5 pts) We can improve the program usability by adding the following functions: - A function is_prime that receives an integer as parameter, check if this integer is a prime number and returns a boolean value depending on the result. - A function find_primes that receives the user sequence as parameter and use the function is_prime to figure out which are the prime values. The function then returns a list containing all the prime values contained in the user sequence. Your user input script should be similar as in part 1 and use the result of the find_primes function to display the list of prime numbers.

Answer 1

#include <iostream>
using namespace std;

bool is_prime( int num)
{
// Corner case
if (num <= 1)
return false;

// Check from 2 to n-1
for (int i = 2; i < num; i++)
if (num % i == 0)
return false;

return true;
}

int* find_primes(int* arr,int* i) // find prime numbers in the list
{
static int parr[100]; // parr is the list prime numbers
int k = 0;

for(int j = 0; j < *i; j++) // check all elements
{
if(is_prime(arr[j])) // if prime or not
parr[k++] = arr[j]; // if prime then store in prime list
}

*i = k; // number of primes in prime list

return parr;
}

int main()
{
int integers[100], num, i, prime[100];
int* pint;

cout << "Enter list of positive integers ( -1 to terminate ) : " << endl;

for(i = 0; i < 100 ; )
{
cin >> num;
if (num == -1) // if user enter -1 then go out from loop
break;
if (num < 0) // if user enter negative integer do not take it
continue;
integers[i++] = num; // if user enter positive integer store it
}

cout << "Prime numbers are : " << endl;
pint = find_primes(integers,&i); // call the find_primes function

for(int j = 0; j < i; j++) // print the prime numbers
cout << pint[j] <<endl;

return 0;
}