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

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

您可以在想要结束程序的地方使用exit()，它在您的情况下工作得很好。但到目前为止，最好的方法是返回一个值来测试延续，这是最具可读性的。

#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返回类型:

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

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

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