时间戳

首页 > 解决方案 > 查找两个区间之间的素数的函数

c++ - 查找两个区间之间的素数的函数

问题描述

我已经编写了大部分程序，我只是在调试它时遇到了麻烦。我对素数的计算一定有问题。对于我尝试的任何事情，它都说有 0 个素数。任何帮助将不胜感激。代码和输出如下。注意：对于这个程序，我不允许使用向量或数组。

#include <iostream>
#include <cmath>

using namespace std;

// FUNCTION PROTOTYPE FOR read_range
   void read_range(int &lower, int &upper);
// FUNCTION PROTOTYPE FOR is_prime
   bool is_prime(const int num);
// FUNCTION PROTOTYPE FOR display_primes
   void display_primes(const string &prime, const int lower, const int upper);
// DO NOT MODIFY THE MAIN ROUTINE IN ANY WAY
int main()
{
  int imin(0), imax(0);

  // Read in range
  read_range(imin, imax);

  // Print prime numbers
  cout << endl;
  display_primes("Primes: ", imin, imax);

  return 0;
}

// DEFINE FUNCTION read_range() HERE:
 void read_range(int &lower, int &upper){
     cout << "Enter minimum and maximum: "; 
     cin >> lower >> upper;
     while (lower < 2 || upper < 2 || lower > upper){
         if (lower < 2 || upper < 2) {
            cout << "Error. Minimum and maximum must be at least 2." << endl; }
         else if (lower > upper) {
            cout << "Error. Minimum must be less than maximum." << endl; } 
      cout << "Enter minimum and maximum: "; 
      cin >> lower >> upper; }}

// DEFINE FUNCTION is_prime() HERE:
 bool is_prime(const int num) {
     for (int i = 2; i <= sqrt(num); i++) {
         if (num % i == 0) {
            return 0; }             // Is not prime
         else {
            return 1; }}}           // Is prime

// DEFINE FUNCTION display_primes() HERE:
 void display_primes(const string &prime, const int lower, const int upper) {
   int count = 0;
   int commaCheck = 0;

   for (int i = lower; i <= upper; i++) {
      if (is_prime(i)) {
         count = count + 1; }}
         
   if (count == 1) {
      cout << "There is " << count << " prime number in this range." << endl; }
   else {
      cout << "There are " << count << " prime numbers in this range." << endl; }


   if (count != 0) {
      cout << prime;
      for (int i = lower; i <= upper; i++) {
         if (is_prime(i)) {
            if (count == 1) {
               cout << i;}
            else {
               commaCheck = commaCheck + 1; }
            if (commaCheck != count) {
               cout << i << ","; }
            else {
               cout << i; }}}
            cout << endl; }
   else {
      cout << "No primes to display." << endl; }}

输出（输入为 2,3）

Enter minimum and maximum: 
There are 0 prime numbers in this range.
No primes to display.

标签： c++

解决方案

is_prime有两个问题。

  1. 如果sqrt(num)小于 2，则循环永远不会执行，并且您的函数具有未定义的行为，因为它没有返回就结束（您的编译器可能应该警告您有关此问题）
  2. 如果数字不是偶数，那么在您调用的循环的第一次迭代中，return 1这意味着所有奇数都将被标记为素数。

将循环更改为此将起作用（如果效率不高，有更好的算法来查找素数）：

bool is_prime(const int num) {
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

推荐阅读