5 Answers

New AnswerRoman J I haven't considered time complexity. If that's so, then for loop to sqrt(n) will be even more efficient This will give time complexity of O(sqrt(n))

#include <iostream> using namespace std; int main() { int n, i; bool isPrime = true; cout << "Enter a positive integer: "; cin >> n; for(i = 2; i <= n / 2; ++i) { if(n % i == 0) { isPrime = false; break; } } if (isPrime) cout << "This is a prime number"; else cout << "This is not a prime number"; return 0; }

Make a Prime() function which contains a for loop i in the range between 2 and a num (say n). It will return False if n%i = = 0. and then return True. // will execute only if the above for loop doesn't return anything // In the main function use another for loop in the range 2 to the input num (say p) . so primes are present between 2 and p. int main() { for (i= 2 ; i<p;i++) { if( Prime(i) ==True) cout<<i<<endl; } return 0; }