Discuss Prime Number Finder in the C Programming forum on Dev Shed. Prime Number Finder C programming forum discussing all C derivatives, including C#, C++, Object-C, and even plain old vanilla C. These languages are low level languages, and used on projects such as device drivers, compilers, and even whole computer operating systems.
The ASP Free website provides in-depth information on the latest developer tools available from Microsoft. Our cadre of writers, highly experienced industry experts, reveals the best ways to use established technologies as well as new and emerging technologies. Our coverage of Microsoft's development and administration technologies is among the most respected in the IT industry today.
ASP Free and Iron Speed Designer are giving away $5,500+ in FREE licenses. Iron Speed's RAD CASE toolset can save up to 80% of your coding time. One free license per week, one perpetual license per month! Download and Activate to enter!
Intel® Graphics Performance Analyzers is a powerful tool suite for analyzing and optimizing your games, media, and graphics-intensive applications. Used by some of the best developers on the planet, Intel GPA lets you maximize your app’s performance.
Posts: 2,059
Time spent in forums: 2 Weeks 1 Day 10 h 50 m 52 sec
Reputation Power: 47
Prime Number Finder
I've been trying to make this just for fun; however, it doesn't seem to work.
What it basically 'should' do is find prime numbers within the range of int.
PHP Code:
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int number = -1;
int remainder;
int divisor;
cout<<"Welcome to the Prime Number Finder\n";
cout<<"Press Enter to start";
for (number=-1;number>-2;number++)
{
for (divisor=0;divisor<number;divisor++)
{
remainder = number % divisor;
if (remainder = 0 & divisor != 1)
{
cout<<"NOT:";
}
}
cout<<number;
cin.get();
}
return 0;
}
There 'must' be something wrong, but I can't seem to get it.
Help would be exttremely appreciated!
thanks,
Posts: 6,704
Time spent in forums: 1 Month 6 Days 6 h 45 m 21 sec
Reputation Power: 1233
check you're first "if" statement, you have a single equal sign and ampersand
here is your code, optimized a-la B-Con
Code:
#include <iostream>
using namespace std;
int main()
{
bool prime;
int number,remainder,divisor;
cout<< "Welcome to the Prime Number Finder\n\n";
for (number=0; number < 2147483648; number++) {
prime = true;
for (divisor=2; divisor < number; divisor++) {
if (!(number % divisor)) {
prime = false;
break;
}
}
if (prime)
cout<< number << " is prime\n";
}
cin.get();
return 0;
}
__________________
- "Cryptographically secure linear feedback shift register based stream ciphers" -- a phrase that'll get any party started.
- Why know the ordinary when you can understand the extraordinary?
- Sponsor my caffeine addiction! (36.70 USD received so far -- Latest donor: Mark Foxvog.)
Posts: 6,704
Time spent in forums: 1 Month 6 Days 6 h 45 m 21 sec
Reputation Power: 1233
np
also, change the conditional in you "for" loop to be "divisor<number/2", because by default you know nothing greater than one half of the number will be able to go into it more than once
Posts: 1,042
Time spent in forums: 2 Days 53 m 47 sec
Reputation Power: 11
Quote:
Originally Posted by B-Con
np
also, change the conditional in you "for" loop to be "divisor<number/2", because by default you know nothing greater than one half of the number will be able to go into it more than once
I would use an even more restrictive test: divisor*divisor <= number. On the basis that, if there are two divisors a and b, such that a * b == number and a <= b, then the test ((a*a <= number) || (b*b >= number)) will always be true ......
__________________
It is only our bad temper that we put down to being tired or worried or hungry; we put our good temper down to ourselves."
-- C.S. Lewis
I like long walks, especially when they're taken by people who annoy me.
--Fred Allen
Posts: 2,059
Time spent in forums: 2 Weeks 1 Day 10 h 50 m 52 sec
Reputation Power: 47
instead of putting 2 and doing ++ all the time,
wouldn't it be better to output 1 and 2 in the first time, start with odd number and add 2 all the time since we know only odd numbers are primes?
Posts: 23
Time spent in forums: 10 h 5 m 5 sec
Reputation Power: 0
It is enough to check the condition in your for loop to "divisor< sqrt(number)".
Your code becomes much faster.Because any numbers divisor will surely be less
than the square root of that number.
Posts: 1,042
Time spent in forums: 2 Days 53 m 47 sec
Reputation Power: 11
Quote:
Originally Posted by prs_kishore
It is enough to check the condition in your for loop to "divisor< sqrt(number)".
Depends on your objective. Comparing against sqrt(number) may reduce the number of iterations in the loop, but will be slower overall unless you have a fast means of computing the sqrt(). Checking divisor * divisor < number is an alternate means, which will be faster in some cases.
Quote:
Originally Posted by prs_kishore
Your code becomes much faster.Because any numbers divisor will surely be less than the square root of that number.
That is misstated. If number is not prime, then at least one of its factors is guaranteed to be less than sqrt(number).
Posts: 1,713
Time spent in forums: 1 Month 2 Weeks 1 Day 33 m 13 sec
Reputation Power: 1495
As you've probably already read by now, you can get a lot faster results for a given range of numbers with the Sieve of Eratosthenes algorithm (there are other methods for finding very, very large primes, but most of those are probabilistic rather than deterministic). The sieve goes something like this:
Code:
#include <cmath>
/* sieve() - a function that takes an array of booleans
and the size of the array
The function fills the array and returns a pointer to the
array
The caller is responsible for ensuring that the buffer
is at least 'range' size of larger)
*/
bool* sieve(int range, bool[] found)
{
int maxtest;
maxtest = ceil(sqrt(range)); // the largest value that needs to be tested
// pre-set the values of zero and one to false
found[0] = false;
found[1] = false;
// set the remaining values to true by default
// we do not treat 2 as a sepcial case, since the
// mechanism of the algorithm will have the
// same effect anyway.
for (int i = 2; i < range; ++i)
{
found[++i];
}
for (int test = 2; test < maxtest; ++test)
{
// If a value to be tested has not been 'crossed out'
// by the time the loop reaches it, then it is prime.
if (found[test])
{
// when a prime has been found, find each
// multiple of it in the array, and set it to false
for (int lastval = test * 2; lastval < range; lastval += test)
{
found[lastval] = false;
}
}
}
return found;
}
(Note that this is not tested code.)
EDIT: I corrected some minor errors in the code, and added more extensive commentary.
FOR SALE: One ShapeSystem 2300 CMD, extensively modified for human use. Includes s/w for anthro, transgender, sex-appeal enhance, & Gillian Anderson and Jason D. Poit clone forms. Some wear. $4500 obo. tverres@et.ins.gov
Last edited by Schol-R-LEA : January 30th, 2005 at 04:45 AM.
Posts: 2,059
Time spent in forums: 2 Weeks 1 Day 10 h 50 m 52 sec
Reputation Power: 47
Hey,
thanks to all who have posted in the thread, as I did not expect this much!
I have been working on my left-over times and stuff, and this is how far I have gotten...
any suggestions within my level? (beginner -> intermediate)
Code:
#include <iostream>
#include <stdio.h>
#include <conio.h>
using namespace std;
int main()
{
bool prime;
int number, remainder, divisor;
cout<<"Welcome to the PrimeNumberFinder\n";
cout<<"2 is prime\n";
for (number = 3; number < 10000000; number += 2){
prime = true;
for (divisor = 3; divisor < (number / 2); divisor++){
remainder = (number % divisor);
if (remainder == 0){
prime = false;
break;}
}
if (prime == true){
cout<< number << " is a prime\n";
}
}
getch();
return 0;
}
Posts: 2,059
Time spent in forums: 2 Weeks 1 Day 10 h 50 m 52 sec
Reputation Power: 47
it has been a while, but I've been trying to write it on a file.
Output isn't so much of a problem, but I'm trying to make it so it doesnt have to start all over again when it starts. Rather, starting where it left off next time.
any ideas? thanks alot!
PHP Code:
#include <iostream>
#include <fstream.h>
#include <stdio.h>
#include <conio.h>
using namespace std;
int main()
{
bool prime;
int number, remainder, divisor;
cout<<"Welcome to the PrimeNumberFinder\n";
cout<<"Press Enter to continue\n";
getch();
ofstream results("D:/C++ Projects/Prime_Numbers.txt", ios::out);
cout<<"2 is prime\n";
results<<"2 is prime\n";
/* the main loop, the number they test is increased by 2
because only odd numbers are prime after 2 */
for (number = 3; number > 0; number += 2){
prime = true;
/* -Second loop, the number they test with is increased by one
from 3 because we start from 3 */
/* -The conditional statement is checked for the half of the
number because you can only divide by number smaller than
half of the number */
Posts: 542
Time spent in forums: 16 h 58 m 34 sec
Reputation Power: 8
I don't understand what you mean by starting where it left off when you start over. Your program shouldn't stop until you reach the limit of an int. When you start the next time it can't continue from there without working on numbers greater than an int can store.
you only need to find the remainders up to(including) sqrt of number, not all the way up to number/2.
Code:
int numroot= sqrt(number);//find the root of number once instead each time through the nested loop.
for (divisor = 3; divisor <= numroot; divisor++){
remainder = (number % divisor);
Posts: 2,059
Time spent in forums: 2 Weeks 1 Day 10 h 50 m 52 sec
Reputation Power: 47
Quote:
Originally Posted by fisch
I don't understand what you mean by starting where it left off when you start over. Your program shouldn't stop until you reach the limit of an int. When you start the next time it can't continue from there without working on numbers greater than an int can store.
Thanks for the suggestion.
What I am trying to do is this.
Say I do not have enough time to reach the limit of int. What I am trying to do is, when the program writes X is prime, the next time the program is opened, it reads X, and then starts evaluating numbers bigger than X. Then continues writing which numbers are prime.