Write a C++ program that uses an array determine and display the prime numbers between 2 and n

[kyky365]

Hi,i need to write program to print prime number between 1 to n(user input),please give me outline :) I have absolutely no idea :(


Write a C++ program that uses an array of n elements (where n is a user input) to determine
and display the prime numbers between 2 and n using the method described below. Ignore
array elements 0 and 1.

A prime number is any integer greater than one that is divisible only by itself and 1. A list of
prime numbers can be found by the following method.

a) Create a primitive type bool array with all elements initialized to true. Array elements
with prime indices will remain true. All other array elements will eventually be set to
false.

b) Starting with array index 2, determine whether a given element is true. If so, loop
through the remaining of the array and set to false every element whose index is a
multiple of the index for the element with value true.

c) Then continue the process with the next element with value true.
For array index 2, all elements beyond element 2 in the array that have indices which are
multiples of 2 (indices 4, 6, 8, 10, etc.) will be set to false; for array index 3, all elements
beyond element 3 in the array that have indices which are multiples of 3 (indices 6, 9, 12,
15, etc.) will be set to false; and so on.

d) When this process completes, the array elements that are still true indicate that the index
is a prime number. These indices can be displayed.


Multiple sessions of sample screen display when the method is called are given below:
Enter the value of n: 10
Prime numbers: 2, 3, 5, 7
4 primes found.
Enter the value of n: 60
Prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
53, 59
17 primes found.
Enter the value of n: 100
Prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
53, 59, 61, 67, 71, 73, 79, 83, 89, 97
25 primes found.
The input which is underlined is the user’s input to a question. (Note: you don’t have to
repeatedly execute your program code using loop for this assignment)

[mahinkhan22]

good luck doing your homework :)

[o1vk4iN6]

Could use a bit array instead to save some space.

[Peter87]

xerzi wrote:

Could use a bit array instead to save some space.

That is not what he should start worrying about.

@mahinkhan22, do a) first and worry about the other things later. Do you know how to create an array with dynamic length? Do you know how to set all elements to true?

If you know how to use std::vector and you are allowed to use it, use it instead of array.

[kyky365]

I had told to be use array...
sorry I don't know what is std::vector.
I don't know why the n in bool p has an error, said expression must have a constant value

int n;
cin>>n;   
bool p [n];

[Peter87]

The size of an array with automatic storage duration has to be a compile time constant. You will have to dynamically allocate the array if you want a variable size.
bool* p = new bool[n];

Don't forget to free the array when you no longer need it.
delete[] p;

[mahinkhan22]

use

vector

then you don't have to worry about allocating and deleting

[kyky365]

thank you first Peter87 and mahinkhan22

does that

bool* p = new bool[n];
delete[] p;

mean all elements initialized to true?

I don't get it. what is all elements initialized to true

I am sorry mahinkhan22 I can't use vector coz I have not been teached yet.

[Peter87]

No all the elements will be uninitialized. You could use a loop and set all the values to true or use std::fill (if you are allowed).

[webJose]

Clearly the homework is above the OP's level. @kyky365: What happened? Skipped classes? Didn't study? I recommend that you read the tutorial on the C++ language in this website before continuing. Pay special attention to dynamic memory and arrays as this homework seems to require this from you. Forget the advise to use std::vector as it would infringe the rules of the homework.

[therockon7throw]

Hi,

I'm not going to solve the whole problem but just part one (a);

A possible solution

the function

bool isPrime(int n){
	if( n < 2 )
		return false;	
	for(int i = 3; i < n ; i++)
		if( ( ( int) n / i ) * i  == n )
			return false;
	return true;
}

in main ->

bool* p = new bool[n];
for(int i = 0 ; i < n ; i++)
	p[i] = isPrime(i);

//do other calculation and at the end delete [] p ;


or may be the way your teacher wishes

in main ->

bool* p = new bool[n];
for(int i = 0 ; i < n ; i++){
	p[i] =true;
        if( !isPrime(i) )
          p[i] = false;
 }

hope it helps