C++ app occasionally determines a prime integer is composite [SOLVED]

deltaecho · 2009-03-21 00:20:54

I am trying to create a simple C++ app to determine whether each of a set of input integers is prime, however, my application seems to occasionally decide a prime integer is composite. Can anybody see an error in my code? I've compiled it using qmake, if that makes a difference.

#include <iostream>
#include <stdlib.h>
#include <math.h>

using namespace std;

/** Determine whether an integer is prime **/
bool isPrime( const int primetoken )
{
    /* 
     * Test 1:
     *    If the ( floor of the square root of an integer ) squared is the integer itself,
     *    the integer is not prime.
     */
    int root = int( sqrt( primetoken ));
    if (( int )pow( root, 2 ) == primetoken ) {
        return false;
    }

    /*
     * Test 2:
     *    If the integer is > 9 and it ends in 0, 2, 4, 5, 6, or 8,
     *    it is not prime.
     */
    if ( primetoken > 9 ) {
        int current = primetoken % 10;
        switch ( current ) {
            case 0:
            case 2:
            case 4:
                return false;
            default:
                switch( current ) {
                    case 5:
                    case 6:
                    case 8:
                        return false;
                    default:
                        break;
                }
        }
    }

    /*
     * Test 3:
     *    If the sum of the digits of the integer is divisible by 3,
     *    it is not prime.
     */
    if ( primetoken > 9 ) {
        int sum;
        for ( int token = primetoken; token; token /= 10 ) {
            sum += token % 10;
        }
        if ( sum % 3 == 0 ) {
            return false;
        }
    }

    /*
     * Test 4:
     *    If the integer is divisible by any integer up to its square root,
     *    it is not prime.
     */
    if ( primetoken > 2 ) {
        if ( primetoken % 2 == 0 ) {
            return false;
        }

        for ( int index = 3; index <= root; index += 2 ) {
            if ( primetoken % index == 0 ) {
                return false;
            }
        }
    }

    return true;
}

/** Main method **/
int main( int argc, char *argv[] )
{
    for( int index = 1, current; index < argc; index ++ ) {
        if ( isPrime( abs( atoi( argv[ index ])))) {
            cout << argv[ index ] << endl;
        }
    }
}

(03/20/2009-1) Here is an example of how it is failing:

$ for f in $( seq 1 10 ); do ./isprime $( seq 1 100 ) | wc -l; done
25                                                                                                 
25
14
15
25
25
25
25
15
14

'25' is the correct number of prime integers from 0 to 100, and it seems to alternate between 14, 15, and 25. The prime integers that occasionally test as composite seem to be failing at Test 3, where the sum of their digits is sometimes VERY incorrect, such as finding the sum of the digits if 73 as being -1656730230, instead of 10.

(03/20/2009-2) Here is my qmake project file:

######################################################################
# Automatically generated by qmake (2.01a) Fri Mar 20 21:35:09 2009
######################################################################

TEMPLATE = app
TARGET = isprime
DEPENDPATH += .
INCLUDEPATH += .

# Input
SOURCES += main.cpp

Last edited by deltaecho (2009-03-21 02:48:13)

Xyne · 2009-03-21 01:51:52

Could it be a rounding error? Why not add some print statements to see which test is failing? Which false composites is it reporting?

Btw, I would expect your algorithm to yield false positives because it's not comprehensive and defaults to true.

*edit*
Just read your edit. Maybe you could change test 3's "for" condition to

(int token = primetoken; token > 0; token /= 10)

Just to check, "token /= 10" returns an int because token is declared as an int, right? (I don't know c/c++)

*edit 2*
Your code works on my system (compiled with g++).

for f in $( seq 1 10 ); do ./isprime $( seq 1 100 ) | wc -l; done
25
25
25
25
25
25
25
25
25
25

*edit 3*
fixed edit 1

Last edited by Xyne (2009-03-21 02:04:21)

ataraxia · 2009-03-21 02:25:49

In test 3, you never initialize "sum". Who knows what's already in there before you start adding to it?

deltaecho · 2009-03-21 02:43:01

Thanks -- so far, after implementing both your suggestions, it seems to work!!!

I think the problem was the uninitialized sum value, which, as @ataraxia pointed out, was probably using some existing value at whatever memory address it was assigned

Here is the updated code:

#include <iostream>
#include <stdlib.h>
#include <math.h>

using namespace std;

/** Determine whether an integer is prime **/
bool isPrime( const int primetoken )
{
    /*
     * Test 1:
     *    If the ( floor of the square root of an integer ) squared is the integer itself,
     *    the integer is not prime.
     */
    int root = int( sqrt( primetoken ));
    if (( int )pow( root, 2 ) == primetoken ) {
        return false;
    }

    /*
     * Test 2:
     *    If the integer is > 9 and it ends in 0, 2, 4, 5, 6, or 8,
     *    it is not prime.
     */
    if ( primetoken > 9 ) {
        int current = primetoken % 10;
        switch ( current ) {
            case 0:
            case 2:
            case 4:
                return false;
            default:
                switch( current ) {
                    case 5:
                    case 6:
                    case 8:
                        return false;
                    default:
                        break;
                }
        }
    }

    /*
     * Test 3:
     *    If the sum of the digits of the integer is divisible by 3,
     *    it is not prime.
     */
    if ( primetoken > 9 ) {
        int sum = 0;
        for ( int token = primetoken; token > 0; token /= 10 ) {
            sum += token % 10;
        }
        if ( sum % 3 == 0 ) {
            return false;
        }
    }

    /*
     * Test 4:
     *    If the integer is divisible by any integer up to its square root,
     *    it is not prime.
     */
    if ( primetoken > 2 ) {
        if ( primetoken % 2 == 0 ) {
            return false;
        }

        for ( int index = 3; index <= root; index += 2 ) {
            if ( primetoken % index == 0 ) {
                return false;
            }
        }
    }

    return true;
}

/** Main method **/
int main( int argc, char *argv[] )
{
    for( int index = 1, current; index < argc; index ++ ) {
        if ( isPrime( abs( atoi( argv[ index ])))) {
          cout << argv[ index ] << endl;
        }
    }
}

Arch Linux

#1 2009-03-21 00:20:54

C++ app occasionally determines a prime integer is composite [SOLVED]

#2 2009-03-21 01:51:52

Re: C++ app occasionally determines a prime integer is composite [SOLVED]

#3 2009-03-21 02:25:49

Re: C++ app occasionally determines a prime integer is composite [SOLVED]

#4 2009-03-21 02:43:01

Re: C++ app occasionally determines a prime integer is composite [SOLVED]

Board footer