c++ автоматично определя прости числа

Опитвам се да разбера в c++ как да намеря всички прости числа в диапазон (използвайки 100 за сега)

Не съм загрижен за производителността, започвам с C++ и се опитвам да разбера това програмно упражнение от моята книга. Имам моята програма, която се опитвам да използвам по-долу, но тя продължава да връща false. Някакви идеи? Прочетох почти цялата помощ на googles/bing, както и препълването на стека. Мога да напиша код, за да работи с въвеждане на номера; просто не преглеждайте всички числа

някакви идеи какво правя грешно?

#include <iostream>

using namespace std;

bool isPrime(long n);
int main() 
{
    int i;
    //some vars
    char emptyVar;

    //first loop (to increment the number)
    for (i = 0; i <= 100; i++)
    {
        //checking all numbers below 100

        if (isPrime(i) == true)
        {
            //is true
            cout << i << ", ";
        }
        else if (isPrime(i) == false)
        {
            //is false
            cout <<"false , ";
        }
    }
    cin >> emptyVar;
}

bool isPrime(long n)
{
    long i =0;
    //checks to see if the number is a prime
    for (i = 2; i < n; i++) // sqrt is the highest possible factor
    {
        if ( n % i == 0) // when dividing numbers there is no remainder if the numbers are both factors
        {
            // is a factor and not prime
            return false;
        }
        else if (n % i != 0 && i >= 100)
        {
            //is not a factor
            return true;
        }
    }
}

c++ loops boolean numbers primes
person LeviTheDegu    schedule 24.02.2013    source източник
comment
else if (n % i != 0 && i >= 100) трябва да бъде else if (i > n/i).   -  person Will Ness    schedule 25.02.2013

Отговори (3)


arrow_upward
2
arrow_downward

Функцията isPrime няма израз return за всеки възможен път на изпълнение. Например, какво прави isPrime, когато n == 2?

Ето как работи for цикъл (в псевдо код). Общият синтаксис е

for (initialiazion; condition; increment) {
   body;
}
rest;

Това може да се преведе в while-цикъл:

initialiazion;
while (condition) {
  body;
  increment;
}
rest;

По-специално, condition се проверява веднага след intialization, преди да се изпълни body.

Подозирам, че мислите, че for цикъл работи по следния начин:

initialiazion;
do {
  body;
  increment;
} while (condition);
rest;

т.е. условието се проверява след първото increment. Но не става.

person Oswald    schedule 24.02.2013
comment
Така че въз основа на вашите отзиви би било по-подходящо да използвате цикъл while за i ‹ n например и да проверявате всички числа спрямо n, докато сте в този цикъл, по този начин bool може да се върне в цикъла while, ако е фактор и ако има няма фактор, ще излезе от цикъла и след това мога да се върна към основната функция? Предполагам, че има смисъл, трябва да поддържам функцията да работи, докато имам условието true, за разлика от това да правя неща, докато дадено условие е true... - person LeviTheDegu; 25.02.2013
comment
Не исках да предложа някаква конкретна конструкция на цикъл. Със сигурност можете да разрешите проблема с всякакъв вид конструкция на цикъл. Това, което исках да отбележа е, че трябва да знаете точно какво прави вашата конкретна конструкция на цикъл. Различните конструкции на цикли, които C++ предоставя, са основно синтактична захар и често е въпрос на личен вкус коя да се използва. - person Oswald; 25.02.2013

arrow_upward
1
arrow_downward

Трябва да върне true, ако не е фактор от ВСЯКО i, а не само първото, което среща.

bool isPrime(long n)
{
    long i =0;
    //checks to see if the number is a prime
    for (i = 2; i < n ; i++) // sqrt is the highest possible factor
    {
        if ( n % i == 0) // when dividing numbers there is no remainder if the numbers are both factors
        {
            // is a factor and not prime
            return false;
        }
    }
    return true;

}

Също така във вашия случай няма смисъл да търсите отвъд i > n/2. Разбира се, трябва да погледнете литературата, това са наистина стабилни алгоритми за тест за първичност.

person sfotiadis    schedule 24.02.2013
comment
Да, изпълнявах i ‹= sqrt(n); въпреки това се опитвах да опростя изявлението, когато се опитвах да накарам нещата да работят. и как бих изчакал да проверя дали е вярно, докато всичко е сравнено? - person LeviTheDegu; 25.02.2013
comment
Както можете да видите в кода по-горе, той връща true само след като for приключи. Във вашия код връщате true всеки път, когато намерите неделител. - person sfotiadis; 25.02.2013

arrow_upward
0
arrow_downward

Вашата функция isPrime е неправилна. Трябва да провери всички числа и едва след това return true;

И този блок никога няма да бъде извикан при вашите входове:

    else if (n % i != 0 && i >= 100)
    {
        //is not a factor
        return true;
    }
person hate-engine    schedule 24.02.2013
comment
Как щях да чакам дотогава? Трябва ли изявлението за връщане да е просто извън изявлението for? или има нещо друго, което пропускам. the i ›= 100 се опитваше да постигне това, но очевидно не успявам твърде трудно. - person LeviTheDegu; 25.02.2013