-1

I'm writing a code to find the last prime number of a given range. Suppose the range is 1 to 50. Then the last prime no. I want to print must be 47. My idea was to maybe reverse the order of prime numbers in the range and then try printing only the first value. Again kinda like if my order was 1 to 50 then I would start printing from 47, 43 and so on and only print 47. But I'm stuck and not getting ideas on how I could do this. here's my code

int prime_bef(int n)
{
int check = 0;
for (int i = 1; i <= n; i++)
{
    if (n % i == 0)
    {
        check++;
    }
}
if (check == 2)
{
    cout << n << " ";
}

return 0;
}

int main ()
{
   int l; 
   int u;
   cin >> l >> u;

   for (int i = u; i >= l; i--)
   {
      prime_bef(i);
   }

   return 0;
}
Suryansh Singh
  • 1,123
  • 7
  • 15
NerdNet
  • 359
  • 1
  • 3
  • 11
  • *"But I'm stuck"* -- stuck on what? It looks like you have code that does something. Which specifically are you stuck on? Does the code not compile? Does it spit out the _Encyclopedia Britannica_ instead of prime numbers? Something in between? – JaMiT Aug 28 '21 at 04:58

4 Answers4

1

Here is a simple and efficient way to check if the number is prime. I am checking if the number is prime and when it is true I am printing the number and breaking the loop so that only 1 number is printed. You can always remove the break statement and print all prime numbers in range.

#include<iostream>

using namespace std;

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

int main (){
    int l, u;
    cin>>l>>u;  
    for (int i = u; i >= l; i--){
        if(isPrime(i)){
            cout<<i<<"\n";
            break;
        }
    }
    return 0;   
}
virteanchi
  • 169
  • 1
  • 14
  • It works perfectly. One thing I don't get is the for loop line in the bool function. what's the purpose of writing (i*i – NerdNet Aug 28 '21 at 05:07
  • 1
    Yes, it is `i*i<=n`. It is maths. Just try to simulate the process with pen and paper. – virteanchi Aug 28 '21 at 05:08
1

You can just use exit() in the place you want to end the program, and it works fine in your case. But by far the best approach is returning a value to test for continuation, it is the most readable.

#include<iostream>
#include <stdlib.h>
using namespace std;
int prime_bef(int n)
{
int check = 0;
for (int i = 1; i <= n; i++)
{
    if (n % i == 0)
    {
        check++;
    }
}
if (check == 2)
{
    cout << n << " ";
    exit(0);
}

return 0;
}

int main ()
{
   int l; 
   int u;
   cin >> l >> u;

   for (int i = u; i >= l; i--)
   {
      prime_bef(i);
   }

   return 0;
}

Same code using bool return type:

#include<iostream>
using namespace std;
bool prime_bef(int n)
{
int check = 0;
for (int i = 1; i <= n; i++)
{
    if (n % i == 0)
    {
        check++;
    }
}
if (check == 2)
{
    cout << n << " ";
    return true;
}

return false;
}

int main ()
{
   int l; 
   int u;
   cin >> l >> u;

   for (int i = u; i >= l; i--)
   {
      if(prime_bef(i))
        break;
   }

   return 0;
}
Suryansh Singh
  • 1,123
  • 7
  • 15
  • 2
    See [Why should I not #include ?](https://stackoverflow.com/q/31816095) and [Why using namespace std is bad practice](https://stackoverflow.com/questions/1452721). I think it is worse to see those horrors in answers than questions, because answers have the goal to be examples. – prapin Aug 28 '21 at 07:54
0

I'll give you a hint... while you are iteratively checking for the prime nature of the number, also check whether the last prime number calculated in the loop is greater than the max term of the range and break the loop when the condition becomes false.

Dharman
  • 30,962
  • 25
  • 85
  • 135
TechnosapienAI
  • 11
  • 2
0

Here a C++17 approach :

#include <cmath>
#include <iostream>
#include <vector>

// type to use for storing primes 
using prime_t = unsigned long;

// there is a way to determine an upper bound to the number of primes smaller then a maximum number. 
// See : https://primes.utm.edu/howmany.html
// this can be used to estimate the size of the output buffer (vector)
prime_t pi_n(const prime_t max)
{
    prime_t pi_n{ max };

    if (max > 10)
    {
        auto ln_n = std::log(static_cast<double>(max));
        auto value = static_cast<double>(max) / (ln_n - 1.0);
        pi_n = static_cast<prime_t>(value + 0.5);
    }

    return pi_n;
}

// Calculate prime numbers smaller then max
// https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
auto calculate_primes(const prime_t max)
{
    std::vector<bool> is_primes(max, true);

    // 0, 1 are not primes
    is_primes[0] = false;
    is_primes[1] = false;

    // sieve
    for (prime_t n = prime_t{ 2 }; n < prime_t{ max }; ++n)
    {
        if (is_primes[n])
        {
            auto n2 = n * n;
            for (prime_t m = n2; m < max; m += n)
            {
                is_primes[m] = false;
            }
        }
    }

    // avoid unnecessary resizes of vector by pre-allocating enough entries to hold result
    prime_t n{ 0 };
    std::vector<prime_t> primes;
    primes.reserve(pi_n(max));

    // add all prime numbers found by the sieve
    for (const auto is_prime : is_primes)
    {
        if (is_prime) primes.push_back(n);
        n++;
    }

    return primes;
}

int main()
{
    const prime_t max{ 50 };
    auto primes = calculate_primes(max);
    // max prime is last one in container
    auto max_prime = primes.back();
    std::cout << "maximum prime number smaller then " << max << ", is " << max_prime << std::endl;
}
Pepijn Kramer
  • 9,356
  • 2
  • 8
  • 19