Prime numbers c++

Question

I have this code:

#include <iostream>
#include <cmath>

using namespace std;

int n, liczba;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> liczba;
        if (liczba < 2) {
            cout << "NIE" << endl;
        } else if (liczba == 2) {
            cout << "TAK" << endl;
        }

        for (int i = 2; i < liczba; i++) {
            if (liczba % i == 0) {
                cout << "NIE" << endl;
                break;
            } else if (liczba % i != 0) {
                cout << "TAK" << endl;
                break;
            }
        }
    }
    return 0;
}

This program is supposed to write yes "TAK" or no "NIE" whether the number you input is prime or isn't. Variable n is the number of numbers you want to input into program, and liczba is the number you want to check if it's prime or not. It seems to work fine expect one significant thing. If I input number 9 it says yes "TAK" instead of no "NIE".. I discovered that this happens to numbers: 9,27,45,63,81 and so on.. if I add 18 starting from 9 it will happen every time.

What's wrong with my code?

You have not used a flag and thus it says NIE after first check — Vaibhav Bajaj, Jul 28 '16 at 20:38
Potentially useful: https://en.wikipedia.org/wiki/Primality_test — Jesper Juhl, Jul 28 '16 at 20:40
@Vaibhav Bajaj can u explain a little simplier? I dont understand you, im beginner at c++, I dont know what flag is.. :/ — Konradek, Jul 28 '16 at 20:42
All your for loop is doing is checking if the number is odd. (It always breaks out of the first iteration of the loop) — zdan, Jul 28 '16 at 20:42
@Konradek If you're a beginner a probably better strategy to learn c++ is to work through a textbook, rather than asking confused question at Stack Overflow. — πάντα ῥεῖ, Jul 28 '16 at 20:43
Possible duplicate of [Determining if a number is prime](http://stackoverflow.com/questions/4424374/determining-if-a-number-is-prime) — Khalil Khalaf, Jul 28 '16 at 20:48
Why the downvotes? The question is clear enough and even has example code showing OP *tried* to solve the problem on his own. — Jesper Juhl, Jul 28 '16 at 20:50
@JesperJuhl may be, because he is using Polish variable names... — Peter VARGA, Jul 29 '16 at 03:32

score 3 · Answer 1 · answered Jul 28 '16 at 20:41

3

You're breaking on BOTH sides of your if() test. Effectly you'll only ever test one divisor:

e.g. liczba = 9

1. if (liczba % 2 == 0) -> if (9 % 2 == 0) -> if (1 == 0) -> false
2. ...jump to else
3. if (liczba % 2 != 0) -> if (9 % 2 != 0) -> if (1 != 0) -> TRUE
4. spit out 'tak' and break out of the loop

You cannot break out of the loop "early" if you get a remainder. That means the divisor you tested is NOT a factor of the number. You can only break early if you DO get a remainder of 0, which means the number's not prime - it's composite.

answered Jul 28 '16 at 20:41

Marc B

356,200
43
426
500

Thanks for help, to all of You guys! :) It is brighter to me now ;) How to start my adventure with C++? I have book but I would rather do something interactive like Codecademy? I know that there is no course on Codecademy but I just gave an example. I know it may sound rash or reckless but I've read couple of pages of this book (about 120 I guess) and I would code something myself rather than only acquire knowledge without practical use. What do You think? – Konradek Jul 28 '16 at 21:06

score 3 · Answer 2 · edited May 23 '17 at 10:28

3

Hint:

All prime numbers (except 2 and 3) can be expressed in the form 6k+1 or 6k-1, where k is a positive whole number.

Therefore, This should work:

bool IsPrime( int number )
{

 if ( ( (!(number & 1)) && number != 2 ) || (number < 2) || (number % 3 == 0 && number != 3) )
      return (false);

 for( int k = 1; 36*k*k-12*k < number;++k)
     if ( (number % (6*k+1) == 0) || (number % (6*k-1) == 0) )
         return (false);
     return true;
}

Taken from Determining if a number is prime.

edited May 23 '17 at 10:28

Community

1
1

answered Jul 28 '16 at 20:44

Khalil Khalaf

9,259
11
62
104

If it is, then he could use other answers. Yours looks fine right? – Khalil Khalaf Jul 28 '16 at 20:46
2

I think its okayish... Thanks for your answer. I would like to use it as it sure will greatly improve efficiency. Currently I scanned till square root N. – Vaibhav Bajaj Jul 28 '16 at 20:49
1

and of cousre, there's NO point in scanning even numbers, just start testing at 3 and do `i=i+2`. – Marc B Jul 28 '16 at 20:59
@MarcB Yeah, that too halved time taken. – Vaibhav Bajaj Jul 28 '16 at 21:11

score 1 · Answer 3 · answered Jul 28 '16 at 20:42

You have not used a flag and thus it says NIE after first check. Also, you are missing an else statement. Try this instead:

#include <iostream>
#include <cmath>
using namespace std;
int n,liczba;
int main()
{
    cin >> n; //
    for(int i=0;i<n;i++)
        {
            cin>>liczba;
            if (liczba < 2)
                {
                cout << "NIE" << endl;
                }
            else if (liczba == 2)
            {
                cout << "TAK" << endl;
            }
            else
            {
                bool isPrime = true;
                for (int i=2;i<liczba;i++)
                {

                    if (liczba % i == 0)
                        {
                            isPrime = false;
                            break;
                        } 
                }
                if(isPrime)
                    cout<<"TAK";
                else
                    cout<<"NIE";
            }

        }
    return 0;
}

Currently, if you input 7, It will check if 7 % 2 == 0. Since it is not, it will print "NIE" and break out of the loop.

Prime numbers c++

3 Answers3

Linked