Cheat Engine :: View topic - C++ Program to find prime numbers [ FINISHED ! ]

Cheat Engine
The Official Site of Cheat Engine

FAQ

Memberlist

Usergroups

Profile

C++ Program to find prime numbers [ FINISHED ! ]
Goto page 1, 2 Next

Cheat Engine Forum Index -> General programming

View previous topic :: View next topic

Author

Message

educofu
Expert Cheater

Reputation: 3

Joined: 21 Aug 2009
Posts: 171
Location: Brazil,MG,OP

Posted: Tue Dec 14, 2010 1:04 pm Post subject: C++ Program to find prime numbers [ FINISHED ! ]

im current developing a small program to find prime numbers trough brute force:

Code:

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

int d=2;
int n=3;

int main()
{
while(n%d!=0)d++;
if (d==n)
{
cout << n << "\n";
n++;
d=2;
}
main();
}

but it doesnt works...

it was supposed to print prime numbers (increasing)

can some1 help me?

edit--

just finished the program!

here it is:

Code:

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

unsigned long long d=2;
unsigned long long n;
unsigned long long m;
int cont=1;

void cs ()
{system("CLS");}

int main()
{
cout << "Prime numbers generator by EdCoFu!\n\n";
while(cont==1)
{
cout << "Enter initial value: ";
cin >> n;
if (n<=1)n=2;
cout << "Enter maximum value: ";
cin >> m;
cout << endl;
while(n<=m)
{
if(n%d==0)
{
n++;
d=2;
}
else d++;
if (d==n) cout << n << endl;
}
cout << "\nEnter 1 to repeat or 0 to end.";
cin >> cont;
cs();
}
exit(0);
}

after 500000000 it gets rly slow... but works!

heres the binary: http://ifile.it/ict47fn

output example:

Code:

Prime numbers generator by EdCoFu!

Enter initial value: 50
Enter maximum value: 90

53
59
61
67
71
73
79
83
89

Enter 1 to repeat or 0 to end.

_________________

"I finally started thinking outside of the box, only to find myself in a larger box."

Last edited by educofu on Wed Dec 15, 2010 11:44 am; edited 2 times in total

Stylo
Grandmaster Cheater Supreme

Reputation: 3

Joined: 16 May 2007
Posts: 1073
Location: Israel

Posted: Tue Dec 14, 2010 1:21 pm Post subject:

First of all you can use

Code:

cout << n << endl;

instead of using \n since you're using iostream library

second, of course it won't print the numbers, because
when it gets to an even number( lets take 4 ) it won't enter the loop and won't enter the condition, but it'll remain 4 and 2
so it will call main over and over again infinite
_________________

Stylo

NoMercy
Master Cheater

Reputation: 1

Joined: 09 Feb 2009
Posts: 289

Posted: Wed Dec 15, 2010 1:21 am Post subject:

get rid of Main(), call the function x in function x, is bad habbit:)

Slugsnack
Grandmaster Cheater Supreme

Reputation: 71

Joined: 24 Jan 2007
Posts: 1857

Posted: Wed Dec 15, 2010 4:37 am Post subject:

NoMercy wrote:

get rid of Main(), call the function x in function x, is bad habbit:)

Recursion is not a bad habit. Recursion of main is however considered bad.

hcavolsdsadgadsg
I'm a spammer

Reputation: 26

Joined: 11 Jun 2007
Posts: 5801

Posted: Wed Dec 15, 2010 5:41 am Post subject:

It's also against the standard, for what it's worth recursive main is a good way overflow your stack.

NoMercy
Master Cheater

Reputation: 1

Joined: 09 Feb 2009
Posts: 289

Posted: Wed Dec 15, 2010 5:58 am Post subject:

Slugsnack wrote:

NoMercy wrote:

get rid of Main(), call the function x in function x, is bad habbit:)

Recursion is not a bad habit. Recursion of main is however considered bad.

The book by bjorn strasoup says differnt. Well idk, but I use what it tells me to do.

atom0s
Moderator

Reputation: 204

Joined: 25 Jan 2006
Posts: 8579
Location: 127.0.0.1

Posted: Wed Dec 15, 2010 12:47 pm Post subject:

Here's a faster method using caching:

Code:

#include <Windows.h>
#include <bitset>

int __cdecl main( int argc, TCHAR* argv[] )
{
std::bitset< 10000 > primeCache;

// Initialize the bitset to true.
primeCache.reset( );
primeCache.flip( );

// Initialize pos 0, 1 to false.
primeCache.set( 0, false );
primeCache.set( 1, false );

// Initialize rest of cache.
for( int x = 0; x * x < static_cast< int >( primeCache.size() ); x++ )
{
   if( primeCache.test( x ) )
   {
      for( int y = x * x; y < static_cast< int >( primeCache.size() ); y += x )
         primeCache.set( y, false );
   }
}

/**
* Output of prime numbers.
*
*/

#define START_NUM 1
#define FINISH_NUM 1000

// Safety checks etc.
if( FINISH_NUM <= START_NUM )
   return 0;
if( FINISH_NUM > primeCache.size() )
   return 0;

// Print numbers.
for( int z = START_NUM; z <= FINISH_NUM; z++ )
{
   printf( "%d: %s\r\n", z, ( primeCache.test( z ) == true ) ? "true" : "false" );
}

return 0;
}

I wrote this based off of:
http://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/1043247#1043247

Using a cached set of numbers will result in a much faster application. The only real delay is the print out.
_________________

- Retired.

educofu
Expert Cheater

Reputation: 3

Joined: 21 Aug 2009
Posts: 171
Location: Brazil,MG,OP

Posted: Wed Dec 15, 2010 4:13 pm Post subject:

uhm... got to study that ^^ ty wiccan _________________ "I finally started thinking outside of the box, only to find myself in a larger box."

sangeli
Master Cheater

Reputation: 0

Joined: 07 Dec 2006
Posts: 406

Posted: Wed Dec 15, 2010 5:31 pm Post subject:

I didn't read into the other posts very much but remember that you only need to count up to the square root of the number to look for multiples. should save time.
_________________

Dark Byte wrote:

ce can certainly damage hardware let's say you have a robotarm attached to your computer, and the software limits usually block it from ripping out it's own cpu. If you remove that limit and then issue the command to rip out the cpu, sure, say goodbye to your hardware

manc
Grandmaster Cheater

Reputation: 1

Joined: 16 Jun 2006
Posts: 551

Posted: Wed Dec 15, 2010 8:59 pm Post subject:

Heres another method for funsies

Quote:

The Sieve of Eratosthenes... A prime integer is any integer that is evenly divisible only by itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. The algorithm follows:

1. Create an array with all elements initialized to 1 (true). Array elements with prime subscripts will remain 1 and all other elements will eventually be set to zero. We ignore elements 0 and 1 in this exercise.

2. Starting with array subscript 2, every time an array element whose value is 1, loop through the remainder of the array and set to zero every element whose subscript is a multiple of the subscript for the element with value 1.

For array subscript 2, all elements beyond 2 in the array that are multiples of 2 will be set to zero. (elements with subscripts 4,6,8,10... will be set to 0); for array subscript 3, all elements beyond 3 in the array that are multiples of 3 will be set to zero (elements with subscripts 6,9,12,15... will be set to 0) and so on...

When this process is complete, the array elements that are still 1 indicate that the subscript is a prime number. These subscripts can be printed. Ignore the element 0 of the array.

Code available if wanted...lol
_________________

HomerSexual
Grandmaster Cheater Supreme

Reputation: 5

Joined: 03 Feb 2007
Posts: 1657

Posted: Thu Dec 16, 2010 6:51 am Post subject:

Wiccaan wrote:

Here's a faster method using caching:

Code:

// Initialize pos 0, 1 to false.
primeCache.set( 0, false );
primeCache.set( 1, false );

I'm confused by these lines
_________________

educofu
Expert Cheater

Reputation: 3

Joined: 21 Aug 2009
Posts: 171
Location: Brazil,MG,OP

Posted: Thu Dec 16, 2010 10:29 am Post subject:

sangeli wrote:

I didn't read into the other posts very much but remember that you only need to count up to the square root of the number to look for multiples. should save time.

didnt work. but counting up to the half of the number does.
_________________

"I finally started thinking outside of the box, only to find myself in a larger box."

atom0s
Moderator

Reputation: 204

Joined: 25 Jan 2006
Posts: 8579
Location: 127.0.0.1

Posted: Thu Dec 16, 2010 11:51 am Post subject:

HomerSexual wrote:

Code:

// Initialize pos 0, 1 to false.
primeCache.set( 0, false );
primeCache.set( 1, false );

I'm confused by these lines

Not sure if you are confused by the code itself or my wording of it. By saying pos 0, 1 I didn't mean like a graph or anything, meant 0 and 1 are both not prime so their positions inside the bit array are set to false manually.

Not setting 0 manually will cause the first loops test to succeed when x = 0, turning the second loop into an infinite loop due to the stepping.
y += x will never properly step if x is 0 so it will never continue.

Not setting 1 manually will cause the full array to set to false. Instead of stepping the proper x * x + y which should multiply forward it steps every number because x = 1, so you land up with y = x * x, y += x, 1 * 1 + 1 = 2, 2 + 1 = 3, 3 + 1 etc. so it will end up stepping every number in the bitset.

(This is not including the theory that 0 is/isn't prime and/or is/isn't a number and all that fun jazz.)
_________________

- Retired.

Slugsnack
Grandmaster Cheater Supreme

Reputation: 71

Joined: 24 Jan 2007
Posts: 1857

Posted: Fri Dec 17, 2010 1:22 am Post subject:

educofu wrote:

sangeli wrote:

I didn't read into the other posts very much but remember that you only need to count up to the square root of the number to look for multiples. should save time.

didnt work. but counting up to the half of the number does.

You don't need to count up to half. Counting up to the ceiling of the square root will do.

Flyte
Peanuts!!!!

Reputation: 6

Joined: 19 Apr 2006
Posts: 1887
Location: Canada

Posted: Fri Dec 17, 2010 2:02 am Post subject:

Bitches don't know 'bout template meta-programming.

Code:

#include <iostream>

template <unsigned int N>
struct Prime {
template <unsigned int X = 2>
struct Tester {
   enum {
      IsPrime = (N % X) ? Tester<X+1>::IsPrime : 0
   };
};

template <>
struct Tester<N> {
   enum {
      IsPrime = 1
   };
};
};

template <>
struct Prime<1> {
template <unsigned int X = 0>
struct Tester {
   enum {
      IsPrime = 1
   };
};
};

template <unsigned int Low, unsigned int High>
struct Primes {
template <unsigned int N = Low>
struct Printer {
   static void Print() {
      if(Prime<N>::Tester<>::IsPrime) {
         std::cout << N << ", ";
      }
      Printer<N+1>::Print();
   }
};

template <>
struct Printer<High+1> {
   static void Print() {
      std::cout << "done." << std::endl;
   }
};
};

int main()
{
Primes<1, 200>::Printer<>::Print();
return 0;
}

Constant time, yo.

Display posts from previous:

	Cheat Engine Forum Index -> General programming	All times are GMT - 6 Hours Goto page 1, 2 Next
Page 1 of 2

Jump to:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum