Lost Password?

Go Back   CodeCall Programming Forum > Software Development > C and C++

C and C++ C and C++ forum for discussing all forms of C except for C#. These languages are powerful low level languages used for creating Operating Systems, Device Drivers, compilers and much more.

Reply
 
LinkBack Thread Tools Search this Thread Display Modes
  #1 (permalink)  
Old 08-15-2007, 01:45 AM
saurav saurav is offline
Newbie
 
Join Date: Aug 2007
Posts: 8
Rep Power: 0
saurav is on a distinguished road
Default problem with large numbers

Hello,
I am trying to develop a c++ program that would, given any integer, decide whether it is prime. My program responds for small numbers, but doesn't if the number is great enough!

Consider this code, which is very basic, and which responds for n=11117, but falls through (hangs) for 111127

Code:
#include<iostream>
#include<cmath>
using namespace std;
bool divisibility(int i,int j)
{float k; k=float(j);
if(i==0) return false;
else if(j/i ==k/i) return true;
else return false;}

int gcd(int i,int j)
{ 
if(divisibility(i,j)==true) return i;
else if(divisibility(j,i)==true) return j;
else if(i==1||j==1) return 1;
else    {
	int k,l; if(j<i) k=j;else k=i;
	
	if(k>0)
		{while(k>0)
		{if(divisibility(k,i)==true&&divisibility(k,j)==true) return k;
		else k--;}				
		}
	else return 1;
	}
}




bool coprime(int i,int j)
{if(gcd(i,j)==1) return true;
else return false;}



bool primeness(int n)
{int i;
if(n>1)
{int i=1; if((i-1)<n/2){while((i-1)<=n/2){if(coprime(i,n)==true){if((i-1)==n/2)return true;else i++;}else return false;}}}
else return false;
}

int prime(int n)
{int i=n-1;int j;
if(n>1) {j=prime(n-1)+1;
	
	while(i>0)	{if(coprime(prime(i),j)==true)
				{if(i==1) return j; else i--;}
			else {i=n-1;j++;}
			}
	}

else return 2;
 	
}

int main()
{int n;
cout<<"n="<<endl; cin>>n;
if(primeness(n)==true) cout<<"prime"<<endl;

return 0;

}
The following program responds correctly for n=1318699, which is prime and n=1318690, which is not; but it tells that 111111111112 is prime, which the number is not! Why is the problem?

Code:
#include<iostream>
#include<cmath>

using namespace std;

bool primeness(int m)
{int i=2;float k,y;int j;
y=m;
bool pr=true;
while(i<=m/2)
{k=y/i;j=m/i;
if(j==k) pr= false;
i++;}
return (pr);
}

int main()
{int n;
cout<<"n="<<endl; cin>>n;
if(primeness(n)==true) cout<<"prime"<<endl;

return 0;

}

Thanks,
Saurav
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote

Sponsored Links
  #2 (permalink)  
Old 08-15-2007, 11:36 AM
WingedPanther's Avatar   
WingedPanther WingedPanther is offline
Super Moderator
 
Join Date: Jul 2006
Age: 35
Posts: 2,057
Last Blog:
wxWidgets is NOT code ...
Rep Power: 24
WingedPanther is a jewel in the roughWingedPanther is a jewel in the roughWingedPanther is a jewel in the roughWingedPanther is a jewel in the rough
Default

First issue: your code is hard to read, because of the formatting.
Second issue: you are comparing floats, which is fairly dangerous, instead of using modulo division to test divisibility.

Quote:
Originally Posted by saurav View Post
Hello,
I am trying to develop a c++ program that would, given any integer, decide whether it is prime. My program responds for small numbers, but doesn't if the number is great enough!

Consider this code, which is very basic, and which responds for n=11117, but falls through (hangs) for 111127

Code:
#include<iostream>
#include<cmath>
using namespace std;
bool divisibility(int i,int j)  //this function is unnecessary.  Use modular division
{float k; k=float(j);
if(i==0) return false; 
else if(j/i ==k/i) return true;
else return false;}

int gcd(int i,int j)
{ 
if(divisibility(i,j)==true) return i;
else if(divisibility(j,i)==true) return j;
else if(i==1||j==1) return 1;
else    {
	int k,l; if(j<i) k=j;else k=i;
	
	if(k>0)
		{while(k>0)
		{if(divisibility(k,i)==true&&divisibility(k,j)==true) return k;
		else k--;}				
		}
	else return 1;
	}
}




bool coprime(int i,int j)
{if(gcd(i,j)==1) return true;
else return false;}



bool primeness(int n)  //see below for example of clearer indenting
{
  int i;
  if(n>1)
  {
    int i=1;   
    if((i-1)<n/2)
    {
      while((i-1)<=n/2)
      {
        if(coprime(i,n)==true)
        {
          if((i-1)==n/2) return true;
          else i++;
        }
        else return false;
      }
    }
  }
  else return false;
}

int prime(int n)
{int i=n-1;int j;
if(n>1) {j=prime(n-1)+1;
	
	while(i>0)	{if(coprime(prime(i),j)==true)  //why check coprime?  you will run into a divisor before a non-divisor non-coprime number?
				{if(i==1) return j; else i--;}
			else {i=n-1;j++;}
			}
	}

else return 2;
 	
}

int main()
{int n;
cout<<"n="<<endl; cin>>n;
if(primeness(n)==true) cout<<"prime"<<endl;

return 0;

}
The following program responds correctly for n=1318699, which is prime and n=1318690, which is not; but it tells that 111111111112 is prime, which the number is not! Why is the problem?

Code:
#include<iostream>
#include<cmath>

using namespace std;

bool primeness(int m)
{
  int i=2;
  float k,y;
  int j;
  y=m;
  bool pr=true;
  while(i<=m/2)
  {
    k=y/i;
    j=m/i;
    f(j==k) pr= false;
    i++;
  }
  return (pr);
}

int main()
{int n;
cout<<"n="<<endl; cin>>n;
if(primeness(n)==true) cout<<"prime"<<endl;

return 0;

}

Thanks,
Saurav
__________________
CodeCall Blog | CodeCall Wiki | Shareware | Linux Forum
Chat with other CodeCall members on IRC; connect to irc.codecall.net and join #codecall
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #3 (permalink)  
Old 09-11-2007, 03:24 PM
kkelly's Avatar   
kkelly kkelly is offline
Learning Programmer
 
Join Date: Sep 2007
Posts: 50
Rep Power: 4
kkelly is on a distinguished road
Default

I definitely wouldn't use floats, and I wouldn't even use ints. Use unsigned ints. Understanding how numbers are handled by the processor is very important if not paramount. There are more than a few standards, and I'm sorry I don't have any links. You might want to google "Floating Point representation", or "numeric representation". Given your ouput, I'm guessing you problems are stemming from truncation, and/or floating point inprecision.
I didn't look through your code, but unless you are implementing an advanced algorithm, searching for primes is a simple matter.
Code:
unsigned int uintNum;			//	The number to test
unsigned int uintMod;			//	The modulus.

bool blIsPrime;				//       Prime? Yes or No
blIsPrime = true;				//	We'll assume it yes, and try to prove it otherwise

uintMod = 2;				//	We'll start at modulo 2 since it is our first potential factor

//	If our modulus is more than half our number we can stop testing.
//	So, while the number may be prime and the modulus is less than half
while ((blIsPrime) && (uintMod <= (uintNum/2)))
{
	//	if the number is in the modulus set it can't be prime
	if (uintNum%uintMod == 0)
	{
		blIsPrime = false;
	}
	else
	{
		//	increment modulus
		uintMod++;
	}
}
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #4 (permalink)  
Old 10-11-2007, 03:11 AM
Patrick Patrick is offline
Programmer
 
Join Date: Sep 2007
Posts: 100
Rep Power: 4
Patrick is on a distinguished road
Default

Anybody got it running here. Whenever I try to decompile it I got some error like blinking of a black window and getting no output. I am using Borland C++ V6.

Any ideas please.
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #5 (permalink)  
Old 10-11-2007, 04:52 PM
kkelly's Avatar   
kkelly kkelly is offline
Learning Programmer
 
Join Date: Sep 2007
Posts: 50
Rep Power: 4
kkelly is on a distinguished road
Default

The above code has no input nor output mechanism. It is just the algorithm. Here a copy that you can copy and paste.
Code:
#include <iostream>

using namespace std;

int main()
{

	unsigned int uintNum;			//	The number to test
	unsigned int uintMod;			//	The modulus.

	bool blIsPrime;				//       Prime? Yes or No
	blIsPrime = true;				//	We'll assume it is prime, and try to prove otherwise

	uintMod = 2;				//	We'll start at modulo 2 since it is our first potential factor

	cout << "Enter Number: ";
	cin >> uintNum;
	cin.get();
	//	If our modulus is more than half our number we can stop testing.
	//	So, while the number may be prime and the modulus is less than half
	while ((blIsPrime) && (uintMod <= (uintNum/2)))
	{
		//	if the number is in the modulus set it can't be prime
		if (uintNum%uintMod == 0)
		{
			blIsPrime = false;
		}
		else
		{
		//	increment modulus
			uintMod++;
		}
	}

	if (blIsPrime)
	{
		cout << uintNum << " is prime.";
	}
	else
	{
		cout << uintNum << " is not prime.";
	}

	cin.get();
	return 0;
}
Remember that the range of an unsigned integer, given that it is 4 bytes, is 0 - 4294967295.
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote

Sponsored Links
Reply



Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On

Similar Threads
Thread Thread Starter Forum Replies Last Post
Peculiar UI Problem Needs Tackling adriyel C# Programming 2 04-06-2008 07:46 AM
i have a problem please help me!!!???? stack Java Help 8 09-22-2007 03:17 PM
[C] Comparison problem Alhazred C and C++ 1 08-29-2007 04:58 AM
Large powers tim1234 C and C++ 5 12-29-2006 11:29 AM
A small problem in the output The_Master C and C++ 3 12-13-2006 12:04 PM


All times are GMT -5. The time now is 06:00 PM.

Contest Stats

Xav ........ 161.68
neerlin ........ 100
satrian ........ 100
delia ........ 100
chili5 ........ 70.08
morefood2001 ........ 42.41
MeTh0Dz|Reb0rn ........ 28.44
RyanTuosto ........ 20
gamiR ........ 19.64
John ........ 14.46

Contest Rules

CodeCall Goal

Goal: 100,000 Posts
Complete: 68%

Ads