打印给定范围的最后一个素数后从函数中跳出循环

Question

我正在编写代码来查找给定范围内的最后一个质数。假设范围是1到50。那么最后一个素数。我想打印必须是 47。我的想法是可能颠倒范围内素数的顺序，然后尝试只打印第一个值。又有点像如果我的订单是 1 到 50，那么我将从 47、43 开始打印，依此类推，只打印 47。但我被卡住了，不知道如何做到这一点。这是我的代码

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;
}

Answer 1

我给你一个提示...当你迭代检查数字的质数性质时，还要检查循环中计算的最后一个质数是否大于范围的最大项并中断条件变为假时的循环。

Answer 2

这里有一个简单有效的方法来检查数字是否为素数。我正在检查数字是否为素数，当它为真时，我正在打印数字并打破循环，以便只打印 1 个数字。您始终可以删除 break 语句并打印范围内的所有素数。

#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;   
}

Answer 3

你可以只在你想结束程序的地方使用exit()，它在你的情况下工作得很好。但到目前为止，最好的方法是 return 测试连续性的值，它是最可读的。

#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;
}

使用 bool return 类型的相同代码：

#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;
}

Answer 4

这里是 C++17 方法：

#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;
}

打印给定范围的最后一个素数后从函数中跳出循环

Breaking out of loop from function after printing the last prime number of a given range

c++

algorithm

primes