Prime numbers generater

[oliviasmithh901]

Hi,

I am working on a project where I need to create a prime numbers output. I am new in C++ and I am new on this forum too.

I just need a simple code where I just cout prme numbers.

Thanks in advance.

[Ganado]

The simplest thing would be to just count up from 2, and print each number that is prime.

So write a function called "bool is_prime(int n)" that returns true/false for if n is a prime.

To check of a number is prime, you should see if it is not divisible by all numbers between 2 and the sqrt(n), inclusive.

You can do better than O(sqrt(n)), though. See, for example, the Sieve of Eratosthenes, but it might be a bit harder to grasp.

[seeplus]

To determine if a number is prime and to display prime numbers, a simple way is:

#include <iostream>
#include <cmath>

bool isprime(int maxno)
{
	if (maxno < 3 || maxno % 2 == 0)
		return maxno == 2;

	for (int i = 3, maxtry = static_cast<int>(sqrt(maxno)); i <= maxtry; i += 2)
		if (maxno % i == 0)
			return false;

	return true;
}

int main()
{
	int pmax {};

	std::cout << "Enter the maximum number for primes: ";
	std::cin >> pmax;

	std::cout << 2;

	for (int p = 3; p < pmax; p += 2)
		if (isprime(p))
			std::cout << ' ' << p;

	std::cout << '\n';
}

Enter the maximum number for primes: 200
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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

[thmm]

It's possible to do it without sqrt:

bool isprime(int maxno)
{
	if (maxno < 3 || maxno % 2 == 0)
		return maxno == 2;

	for (int i = 3; i * i <= maxno; i += 2)
		if (maxno % i == 0)
			return false;

	return true;
}

[seeplus]

Yes, but i * i is now evaluated for every loop iteration whereas sqrt() is evaluated only once at the start of the loop.

[thmm]

Yes, that's true. I wonder what the difference in performance would be.