You are not logged in.
- Topics: Active | Unanswered
#1 2009-03-21 00:20:54
- deltaecho
- Member
- From: Georgia (USA)
- Registered: 2008-08-06
- Posts: 185
C++ app occasionally determines a prime integer is composite [SOLVED]
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.cppLast edited by deltaecho (2009-03-21 02:48:13)
Dylon
Offline
#2 2009-03-21 01:51:52
- Xyne
- Administrator/PM
- Registered: 2008-08-03
- Posts: 6,963
- Website
Re: C++ app occasionally determines a prime integer is composite [SOLVED]
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)
My Arch Linux Stuff • Forum Etiquette • Community Ethos - Arch is not for everyone
Offline
#3 2009-03-21 02:25:49
- ataraxia
- Member
- From: Pittsburgh
- Registered: 2007-05-06
- Posts: 1,553
Re: C++ app occasionally determines a prime integer is composite [SOLVED]
In test 3, you never initialize "sum". Who knows what's already in there before you start adding to it?
Offline
#4 2009-03-21 02:43:01
- deltaecho
- Member
- From: Georgia (USA)
- Registered: 2008-08-06
- Posts: 185
Re: C++ app occasionally determines a prime integer is composite [SOLVED]
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;
}
}
}Dylon
Offline