|
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| ||||||||||||||||||||||||||
![]() |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
|
#1
|
||||
|
||||
|
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:
There 'must' be something wrong, but I can't seem to get it. Help would be exttremely appreciated! thanks, WJK |
|
#2
|
||||
|
||||
|
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.) |
|
#3
|
||||
|
||||
|
Quote:
single equal sign... Ah! how could I make that mistake? thanks alot! WJK |
|
#4
|
||||
|
||||
|
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 ![]() |
|
#5
|
||||
|
||||
|
Quote:
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 |
|
#6
|
||||
|
||||
|
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? I also forgot &&... WJK |
|
#8
|
||||
|
||||
|
good link, coincedintally yesterday I actually started thinking about that very subject, opertune timing
![]() |
|
#9
|
|||
|
|||
|
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. Kishore PRS. |
|
#10
|
||||
|
||||
|
Quote:
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:
That is misstated. If number is not prime, then at least one of its factors is guaranteed to be less than sqrt(number). |
|
#11
|
||||
|
||||
|
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.
__________________
Rev First Speaker Schol-R-LEA;2 JAM LCF ELF KoR KCO BiWM TGIF #define KINSEY (rand() % 7) λ Scheme is the Red Pill Scheme in Short • Understanding the C/C++ Preprocessor Taming Python • A Highly Opinionated Review of Programming Languages for the Novice, v1.1 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. |
|
#12
|
||||
|
||||
|
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;
}
thanks WJK |
|
#13
|
||||
|
||||
|
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:
WJK |
|
#14
|
||||
|
||||
|
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.
Suggestion: Code:
for (divisor = 3; divisor < (number / 2); divisor++){
remainder = (number % divisor);
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);
__________________
http://members.shaw.ca/decksdoneright |
|
#15
|
||||
|
||||
|
Quote:
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. thanks alot! WJK |
![]() |
| Viewing: Dev Shed Forums > Programming Languages > C Programming > Prime Number Finder |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
|
|
|