## Algorithms

Moderators: None (Apply to moderate this forum)
Number of posts: 762

This Forum Only

prime numbers Posted by paa_vvu on 5 Apr 2004 at 7:28 PM
please can anyone give me the algorithms for finding prime numbers below a number, given that number.
Re: prime numbers Posted by sekiz on 29 Apr 2004 at 4:31 PM
: please can anyone give me the algorithms for finding prime numbers below a number, given that number.
:

Hint:If a number is not divisible to any of the prime numbers below itself then it is a prime number too.

Create an array to hold the found prime numbers.
Add the first prime number 2 as the first object of the array.
Create a variable for current value and initialize it to 3.
In a loop which repeats the statements until the variable is updated to the given number take the remainder of the current variable/objects of the array(holds found prime numbers), add the current variable to the array if any of the remainders is equal to zero(this means none of the prime numbers divides the current value) and update the current variable by adding one to it.
After the break of loop you can print out the values in the array and see the prime numbers below the desired number.

I'm a first year computer science student.Sorry if i confused you. This is not an algorithm but i think it can give you a clue about how to solve the problem.
Re: prime numbers Posted by gaetano on 5 May 2004 at 4:05 AM
This message was edited by gaetano at 2004-5-5 4:6:11

please can anyone give me the algorithms for finding prime numbers below a number, given that number.

The maybe easiest implementation for an algorithm which finds primes
in a given range is the so-called "Sieve Of Erathostenes".

- you will find really every prime
- every found prime is 100% a prime

- the array takes a lot of memory
- the computation time is long for high ranges

If you need the "sieve" in another language than C/C++, just use any
search engine. You'll find everything you need ...

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

int
main (void)
{
long	max;
bool	*primes;

cout << " Calculate prime numbers (sieve of Erathostenes)\n\n";
cout << " Highest number to test: ";
cin >> max;

if (max < 2) {
cerr << " Error: Invalid value!\n"
<< "        Number must be greater than 2.\n";
return 1;
}

// Create array and exclude 0 and 1
primes = new bool[max + 1];

// Fill list with all positive integers
for (long i=0; i<=max; i++)
primes[i] = true;

// The testing ...
for (long i=2; i<=max; i++)
for (long j=2; i*j<max; j++)
primes[i*j] = false;

// The index of the array equals the numbers
// If you want to look whether 7 is a prime, just try
// if `(primes[7])'

// Print them
for (long i=2; i<=max; i++)
if (primes[i])
cout << i << endl;

delete[] primes;
return 0;
}
```

Re: prime numbers Posted by indicatoto101 on 10 Nov 2004 at 9:04 PM
: This message was edited by gaetano at 2004-5-5 4:6:11

: please can anyone give me the algorithms for finding prime numbers below a number, given that number.
:

:
:
: The maybe easiest implementation for an algorithm which finds primes
: in a given range is the so-called "Sieve Of Erathostenes".
:
: - you will find really every prime
: - every found prime is 100% a prime
:
: - the array takes a lot of memory
: - the computation time is long for high ranges
:
: If you need the "sieve" in another language than C/C++, just use any
: search engine. You'll find everything you need ...
:

:
:
```
: #include <iostream>
: using namespace std;
:
: int
: main (void)
: {
: 	long	max;
: 	bool	*primes;
:
: 	cout << " Calculate prime numbers (sieve of Erathostenes)\n\n";
: 	cout << " Highest number to test: ";
: 	cin >> max;
:
: 	if (max < 2) {
: 		cerr << " Error: Invalid value!\n"
: 		     << "        Number must be greater than 2.\n";
: 		return 1;
: 	}
:
: 	// Create array and exclude 0 and 1
: 	primes = new bool[max + 1];
:
: 	// Fill list with all positive integers
: 	for (long i=0; i<=max; i++)
: 		primes[i] = true;
:
: 	// The testing ...
: 	for (long i=2; i<=max; i++)
: 		for (long j=2; i*j<max; j++)
: 			primes[i*j] = false;
:
: 	// The index of the array equals the numbers
: 	// If you want to look whether 7 is a prime, just try
: 	// if `(primes[7])'
:
: 	// Print them
: 	for (long i=2; i<=max; i++)
: 		if (primes[i])
: 			cout << i << endl;
:
: 	delete[] primes;
: 	return 0;
: }
: ```

:
:
:

Can you give me some pseudocode to Intel assembly? thanks didn't find it on google

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic