Find Largest Prime Number

[twaynfme]

A Prime Number is a number that is greater than 1 and has just two factors: itself and 1.

Given an integer, N, for N ≥ 2, a common question is, what is the largest prime number which is not larger than N?

Write a program to
Input an integer N, where 2 ≤ N ≤ 10000.
Output the prime number not larger than N.

I have no idea where to even start, I have no experience with prime numbers in coding.

[George P]

Can you write code that asks the user for a number between 2 and 10,000 inclusive and store the entered number in a variable?

[jonnin]

you do it the same way you would do it on paper in a math class.

there are maybe 4 good ways to do this problem.
1) just make a lookup table of the prime numbers from 0-10k and search out the value desired.
2) check each value from N down towards 2 looking for a prime number. slow, but still, only a fraction of a second for these small values.
3) primality test .. just check each value counting down from N. many of these are 100% ensured for small values, eg https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test
4) generate all the primes up to 10k with a sieve, much like #1, and find the required value.
5) this one may also work with the GCD approach. GCD is provided in C++ ... you can make a few values that are the products of the primes, eg 2*3*5*7... and so on, a small number of them will do... and pull the desired value out that way. This one is a little off the beaten path.

[seeplus]

I have no idea where to even start, I have no experience with prime numbers in coding.

There's loads of info on these forum pages and on the Internet in general as to how to generate/find prime numbers.

[Emil Enchev]

Look my other comment for your program...

[againtry]

@OP
See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
There is a sample pseudocode algorithm included that you can use to make a start.
You only have to read down to that algorithm section section and study the logic to the animated graphic to understand what the algorithm is doing.

[seeplus]

Except 2, a prime is always odd and never even. So if you treat 2 as special, then if it's divisible by 2 then it is not prime. For a simple loop algorithm, if you start the loop at 3 then you can increment by 2. The terminating condition is <= sqrt() (calculate outside of the loop). Using both these facts drastically reduces the loop count.

However, for largish numbers the Sieve OF Eratosthenes (see above) is more efficient.

[Emil Enchev]

This is your finished program you want.

#include <iostream>
using namespace std;

int main()
{
	int n{};
	int originalN{};
	for (;;)
	{
		if (n >= 2 && n <= 10000)
			break;
		else
		{
			cout << "Enter an integer N, where 2 <= N <= 10000: ";
			cin >> n;
			if (n >= 2 && n <= 10000)
				break;
			else
			{
				for (;;)
				{
					cout << endl;
					cout << "Your number is not in an interval 2 <= N <= 10000!" << endl;
					cout << "Please enter an integer N, where 2 <= N <= 10000: ";
					cin >> n;
					if (n >= 2 && n <= 10000)
						break;
				}
			}
		}
	}

	bool isPrime{ true };
        originalN = n;


	for (;;)
	{
		isPrime = true;
		for (int i = 2; i*i <= n; i++) 
		{
			if (n % i == 0)
				isPrime = false;
			if (isPrime == false) 
				break;
		}
		if (isPrime == true)
			break;
		else
			n = n - 1;
	}

	cout << endl;
	cout << "The largest prime number which is not larger than " << originalN << " is " << n << " !" << endl;
	return 0;
}

Enter an integer N, where 2 <= N <= 10000: 5789

The largest prime number which is not larger than 5789 is 5783 !

[The Grey Wolf]

Emil Enchev wrote:

Now do you understand how things are done in programming?

First you try to understand what is required of you in its simplest form.

What are the requirements again?

Given an integer, N, for N ≥ 2, a common question is, what is the largest prime number which is not larger than N?

and your solution...

The nubmer 1000000000 is a Composite!
Time: 0 microseconds

🤷‍♂️

[Emil Enchev]

What is your question exactly?

These are the comments that usually make me rub everything I've posted... no one reads them anyway...You are all looking only for the end product.

My solution was given very explicitly... look now the comment, when I removed all other code. Do you see it? Do you test it?

[Duthomhas]

Optimization is totally unnecessary for this.

This is an introductory C++ kind of assignment, which typically asks for a simple concept as code. Note that OP's requirements are simply:

  • accept N as input
  • find p ≤ N such that p is prime
  • print p

This does not even require a function or any other control construct besides the ability to write a loop. A function is really, really helpful in terms of thinking through the assignment though.

Notice how the requirements do not ask us to verify 2 ≤ N ≤ 10000. Rather, it is stated that the input will be within that range. Therefore: don't spend time checking that — it is not part of the assignment to do so.

  int N;
  std::cin >> N;

Done!


The second point separates into two parts:
  • p ≤ N suggests that we need a loop: if p==N is not prime, then check p==N-1, then p==N-2, etc until p is discovered to be prime.
  • code to check whether p is prime.

We can write the loop part easily enough:

  int p = N;
  while (!prime( p ))
  {
    p -= 1;
  }

Again, notice how we don't care to check that N is a "safe" number. Input is expected to be in the range [2, 10000].


Now the hardest part: determining if a number is prime.

Question: is 25 prime?
  - is it evenly divisible by 2? no
  - is it evenly divisible by 3? no
  - is it evenly divisible by 4? no
  - is it evenly divisible by 5? YES
Answer: 25 is not prime.

Question: is 7 prime?
  - is it evenly divisible by 2? no
  - is it evenly divisible by 3? no
  - is it evenly divisible by 4? no
  - is it evenly divisible by 5? no
  - is it evenly divisible by 6? no
  - is it... oh, wait, 7 == 7. we're done.
Answer: 7 is prime.

Again, you should see how this suggests a loop. Start at two and check for even divisibility each time. If you get to the number you are testing then you have yourself a prime number. But if you find an even-divisor you have a composite number. This is where a function really helps:

bool prime( int p )
{
  int n = 2;
  while (n < p)
  {
    if (n evenly divides p)
    {
      return false; // not prime!
    }
    n += 1;
  }
  return true; // prime!
}

The check for even divisibility in C and C++ is using the "remainder" operator (often called the "modulo" or "modulus" operator), because it gives you the remainder of a division instead of the integer quotient:

  p / n   →   integer quotient of p divided by n

  p % n   →   remainder of p divided by n

If the remainder is zero, then you have an even divisor. (You can say that "n divides p".)


The last thing to do is to print your newly-found prime number ≤ N:

  std::cout << p << "\n";

Again, you do not have to care about checking bounds, etc. You know that your input is going to be valid, and all valid inputs satisfy finding a prime number.

C:\Users\twaynfme\cpp> assignment2
2
2

C:\Users\twaynfme\cpp> assignment2
3
3

C:\Users\twaynfme\cpp> assignment2
4
3

C:\Users\twaynfme\cpp> assignment2
5
5

C:\Users\twaynfme\cpp> assignment2
6
5

C:\Users\twaynfme\cpp> assignment2
25
23

Notice how it works. Given a prime number, you get back that same prime number. Given a composite number, you get the next-largest prime number.

The algorithm here to find a prime number can be improved very slightly, but even if not, it is more than fast enough for any integer in [2, 10000].

You can write this without the function, of course, but in my opinion that would make it more difficult to keep things straight in your head. The purpose of the function is to keep separate things separate: backward counting loop in main is a different thing than the loop to determine whether a number is prime or not. Keep the tasks separate in your head and life is simpler.

Hope this helps.

[The Grey Wolf]

Emil Enchev wrote:

These are the comments that usually make me rub everything I've posted..

Wow, a bit of friendly ribbing makes you through your toys out the pram?

[Duthomhas]

Er, are we trying to scare off the beginners or what?

[Emil Enchev]

It is not about a rubbing... its about a people. This forum has long since lost its luster. It used to be a place where people learned C++ from each other. Now it is simply the place where someone just wants someone else to write the program for him/her and he/she to copy and paste it - without learning anything, without even saying thank you in the end ;-)

[Duthomhas]

No, it has always been the same forum. Some people just get big heads here and there. Is that why you are posting a complete solution for the OP? Because the OP did not just ask for a solution. OP asked for help on where to start.

[seeplus]

Perhaps (without input checking):

#include <iostream>
#include <cmath>

int main()
{
	const auto mx {10'000U};
	auto n {0U};

	std::cout << "Enter an integer N (2 - " << mx << "): ";
	std::cin >> n;

	if (n != 2) {
		n -= n % 2 == 0;

		for (bool got {}; !got; n -= 2 * !got) {
			got = true;

			for (auto i {3U}, lst {static_cast<unsigned>(sqrt(n))}; i <= lst; i += 2)
				if (n % i == 0) {
					got = false;
					break;
				}
		}
	}

	std::cout << "The nearest lower prime number is " << n << '\n';
} 

Enter an integer N (2 - 10000): 876
The nearest lower prime number is 863

[seeplus]

As sqrt() is quite an expensive function and only the highest integer result is required, a simple isqrt() function could be used instead of sqrt() to provide better performance.

Perhaps as C++17:

unsigned long isqrt(unsigned long s) {
	if (unsigned long x0 {s >> 1}; x0) {
		for (unsigned long x1 {(x0 + s / x0) >> 1}; x1 < x0; ) {
			x0 = x1;
			x1 = (x0 + s / x0) >> 1;
		}

		return x0;
	}

	return s;
}

[jonnin]

the trick to the babylon method is the initial guess.
for 0-10k, a better guess will nail it in far fewer iterations than you are using with your guess (looks like you get 8-9 iterations for larger values).
unroll it a bit, and you end up with:

unsigned long isqrt(unsigned long s) 
{	
	unsigned long x1 = 1+ s/70;
		
		x1 = (x1 + s / x1) >> 1;		
		x1 = (x1 + s / x1) >> 1;		
		x1 = (x1 + s / x1) >> 1;		
		return x1;	
}



int main()
{   
   int foo[] = {1,5,30,100,250,1001,3003,5007,7520,8888,10000};
   for(int i = 0; i < 11; i++)	   	   
   cout <<foo[i]<<" " <<isqrt(foo[i]) <<" "<<sqrt(foo[i])<< endl; 
}

1 1 1
5 2 2.23607
30 5 5.47723
100 10 10
250 16 15.8114
1001 31 31.6386
3003 54 54.7996
5007 70 70.7602
7520 86 86.7179
8888 94 94.2762
10000 100 100

for > 10k a new initial value would need to be figured out.

all that said, need to time it against the FPU. I havent thought about this stuff since 386 (no FPU type) days... pretty sure
https://www.cplusplus.com/forum/lounge/279501/
is the way to go if you need to do this at all -- can that hack be easily adjusted for just sqrt instead of inverted...? would have to sit down and play with it..
eh-heheh ... he did it for us farther down in the paper.

sqrt from hand waving (less accurate than the 3 iterations of babylon, but hey, its faster)
float f;
unsigned int *i = (unsigned int*)&f;
f = 5007;
*i = 0x1fbd1df5 + (*i >> 1);
cout << (int)f << endl;