-2

This program was supposed to take input of 6 and return the 6th prime and so on. 

#include<iostream>
#include<cmath>
using namespace std;

bool isPrime(int num)
{
int factor=2;
while(factor<=num/2)
{
    if(num%factor==0)
        return false;
    factor++;
}
return true;
}

int main()
{
int num=2, count=0, whichprime;
cin>>whichprime;
while(count<whichprime)
{
    if(isPrime(num)==true)
    {
        count++;
        num++;
    }
}
cout<<num-1;
}

But, it doesn't work (except for the first and second prime). For the rest, the cursor just keeps blinking at the output page. Can somebody point out the mistake?

LoveOfLearning
  • 215
  • 3
  • 10
  • Please describe the way in which it is not working. – Yunnosch Jun 19 '17 at 20:25
  • 4
    You are only incrementing `num` when you have found a prime number, causing the program to loop infinitely, when it reaches `num == 4`. Put `num++` outside the loop. – dhke Jun 19 '17 at 20:27
  • 2
    Have you tried using your debugger?? – Jesper Juhl Jun 19 '17 at 20:27
  • `factor<=num/2` -> `factor*factor<=num` – Yunnosch Jun 19 '17 at 20:28
  • @Yunnosch what's the difference? – LoveOfLearning Jun 19 '17 at 20:30
  • If num is 100, one ends at 50 the other at 10. Both yield correct result. If you have tested 100 until 10, there is no need to test 20, because the result would be 5, which already got tested. – Yunnosch Jun 19 '17 at 20:30
  • @Jesper Juhl Don't know what that means. – LoveOfLearning Jun 19 '17 at 20:31
  • @Yunnosch But is factor*factor<=num sufficient for all numbers – LoveOfLearning Jun 19 '17 at 20:32
  • 2
    @Truth-seek that explains a lot (hint: knowing how to use a debugger is a *must have* skill). Try googling it. Or just read https://www.google.dk/amp/s/ericlippert.com/2014/03/05/how-to-debug-small-programs/amp/ – Jesper Juhl Jun 19 '17 at 20:33
  • If you test n/sqrt(n) you can only get sqrt(n). If you test n/m for m>sqrt(n), the result of n/m must be smaller than m. Anything smaller than m was already tested without finding it to be dividing n. – Yunnosch Jun 19 '17 at 20:34
  • I am not sure about this. But, are troubleshooting questions off-topic @ Stack Overflow? – LoveOfLearning Jun 19 '17 at 20:40
  • @Yunnosch Thanks a lot. The program is a lot faster changing from `factor<=num/2` to `factor*factor<=num` – LoveOfLearning Jun 19 '17 at 20:43
  • @dhke True, only for factor*factor > n > (factor-1)*(factor-1) == factor*factor -2*factor + 1. But definitly true. Thanks for pointing out. – Yunnosch Jun 19 '17 at 20:43
  • @Yunnosch Nah, I was on the wrong track. For `factor * factor` overflow is guarded by it being smaller than `num` ;-). – dhke Jun 19 '17 at 20:46
  • Read [ask] and https://stackoverflow.com/help/on-topic number 1. With several strict conditions met, they are on topic. – Yunnosch Jun 19 '17 at 20:47
  • @Truth-seek Is your google/duckduckgo broken? But ok, here's a link: https://www.gnu.org/software/gdb/ – Jesper Juhl Jun 19 '17 at 20:48
  • https://stackoverflow.com/questions/2069367/how-to-debug-using-gdb and https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ – Yunnosch Jun 19 '17 at 20:50
  • @dhke What is `factor * factor` overflow – LoveOfLearning Jun 19 '17 at 20:56
  • @Truth-seek The variables only have a limited value range. If you calculate the product of two integers, the result may not fit into that value range, causing "oveflow", even if the individual factors do. For 32bit signed numbers, the problem appears at `factor = 46341`, where `factor * factor` is actually a negative value (at least on my system). – dhke Jun 19 '17 at 21:01
  • If factor*factor > MAX_INT > n > (factor-1)*(factor-1) then you get an integer overflow in your loop and (if I guess correctly) thereby an endless loop (after optimisation proposed by me). That is what @dhke was warning me about. So you need to restrict the range of inputs for n or compare factor to round(sqrt(n)). – Yunnosch Jun 19 '17 at 21:02
  • @Truth-Seek - you *really* need to learn how to use a search engine: http://en.cppreference.com/w/cpp/language/operator_arithmetic#Overflows – Jesper Juhl Jun 19 '17 at 21:02

1 Answers1

0

Working version with minimal changes:

#include<iostream>
#include<cmath>
using namespace std;

bool isPrime(int num)
{
int factor=2;
while(factor<=num/2)
{
    if(num%factor==0)
        return false;
    factor++;
}
return true;
}

int main()
{
int num=2, count=0, whichprime;
cin>>whichprime;
while(count<whichprime)
{
    if(isPrime(num)==true)
    {
        count++;
    }
    num++;
}
cout<<num-1;
}

(move num++; out of if statement)

Tav Taroved
  • 14