I have to do a C++ program that accepts a user inputed number and then gives you the prime factors of it....is there a formula to figure this out or is there any other way i can do it??
HELP: Is there a formula to figure out if a number is prime???
- Thread starter yhdd
- Start date
its impossible...and the code i've seen out there to do it, is hundreds upon hundreds of lines....but if you do get it, would you be kind enough to swing it be me too?
I'm thinking you're supposed to use the mod function and loop through all the numbers that lead up to your int value recording the ones that mod = 0. That gives you the common multiples, etc. From there you read in from your array of stored values and evaluate if that number is prime or not... if not prime, you can toss the number and assume it's repeated elsewhere... if prime, you'll write that in to your array of prime numbers to be churned out.... one word of advice, it may make the program faster to multiply rather than divide (not sure how modern c++ interprets that stuff).
-Joe
Edit: The interesting thing about doing it this way is that you don't have to evaluate what the prime factors of each number are, just go through an if/else statement like
while test1<= value {
if test1 mod value = 0 {write test1's source to the array of multipliers} else {test1++}
}
to process your array of multipliers:
still working on this.
readin test2
int possibleprimetest
if possibleprimetest <=test2 {
if possibleprimetest mod test2 = 0 { set array slot of test2 to be -1 which will be ignored in the readin or don't do anything and be sure never to look at that spot again} else {possible primetest ++}
} else {write test2 to array of primes}
Anywho, I think that's on the right track... might need to call ints and set to 2 at start to avoid problems with 1, set the <= to to < or something... I don't want to hit my head against it.
-Joe
Edit: The interesting thing about doing it this way is that you don't have to evaluate what the prime factors of each number are, just go through an if/else statement like
while test1<= value {
if test1 mod value = 0 {write test1's source to the array of multipliers} else {test1++}
}
to process your array of multipliers:
still working on this.
readin test2
int possibleprimetest
if possibleprimetest <=test2 {
if possibleprimetest mod test2 = 0 { set array slot of test2 to be -1 which will be ignored in the readin or don't do anything and be sure never to look at that spot again} else {possible primetest ++}
} else {write test2 to array of primes}
Anywho, I think that's on the right track... might need to call ints and set to 2 at start to avoid problems with 1, set the <= to to < or something... I don't want to hit my head against it.
I really wish I'd taken more than 1.5 semesters of programming, I just didn't want to take data structures.....
postcount++;
postcount++;
I don't know C++ 
I'm guessing the problem is more complicated than this but I had to do a program like this in some other language many years back...
X = number being tested
c = temp variable
For c = 2 to (X - 1)
if X = parse(X/c) then blah
c = c + 1
I'm guessing the problem is more complicated than this but I had to do a program like this in some other language many years back...
X = number being tested
c = temp variable
For c = 2 to (X - 1)
if X = parse(X/c) then blah
c = c + 1
Originally posted by: b0mbrman
I don't know C++
I'm guessing the problem is more complicated than this but I had to do a program like this in some other language many years back...
X = number being tested
c = temp variable
For c = 2 to (X - 1)
if X = parse(X/c) then blah
c = c + 1
thats like a brute force way of doing it right? the class im taking, we're not allowed to brute force, besides with numbers like 19589 it mite take a while to get all the way up there
There are many prime number algorithms out there. Do a search.
The problem is that PROVING a number is prime is VERY computationally expensive for very large numbers. There are algorithms that can say with much less effort that a number is LIKELY to be prime without proving it.
The problem is that PROVING a number is prime is VERY computationally expensive for very large numbers. There are algorithms that can say with much less effort that a number is LIKELY to be prime without proving it.
so simple
a loop that tries to divide the number by every number between 2 and himself -1
...
should be quite fast
a loop that tries to divide the number by every number between 2 and himself -1
...
should be quite fast
DougK62
Diamond Member
- Mar 28, 2001
- 8,035
- 6
- 81
Originally posted by: xospec1alk
Originally posted by: b0mbrman
I don't know C++
I'm guessing the problem is more complicated than this but I had to do a program like this in some other language many years back...
X = number being tested
c = temp variable
For c = 2 to (X - 1)
if X = parse(X/c) then blah
c = c + 1
thats like a brute force way of doing it right? the class im taking, we're not allowed to brute force, besides with numbers like 19589 it mite take a while to get all the way up there
Uhh - that's the way you find a prime number. Can you think of an easier way? You have to check every (or at least most) numbers below a number to see if it's prime.
BTW, this is not "brute force" programming. Try google for the real definition.
I don't think the whole problem is to evaluate if a number is prime, but to only return the prime factors and not have repetition.
There is a theorem called Fermat's Little Theorem that might help you out. It works for almost all numbers .... it fails for Carmichael numbers. I think (I could be wrong here so verify me) that it's if p is a prime that is not a factor of a then a^(p-1) = 1 mod p .... that part is true. The converse is not true always, it fails for Carmichael numbers. So if you have a prime number you can use Fermat's Theorem to test it ... it Fermat's holds then it MIGHT be a prime ... then you can waste time doing the expensive calculation (current best is quadratic sieve) .... hope this helps.
--added-
Just remembered something else .... Carmichael numbers are only valid under Fermat's for certain bases (values of a) .... so what you can do is repeatedly try different bases (like .. 100 or so) and then state that "with a probability of 99%, this is a prime)
--added-
Just remembered something else .... Carmichael numbers are only valid under Fermat's for certain bases (values of a) .... so what you can do is repeatedly try different bases (like .. 100 or so) and then state that "with a probability of 99%, this is a prime)
Where the hell do people get the idea that it's impossible to tell if a number is prime? Or that it's even difficult?
perl:
print "enter a number: ";
$in = <>;
chomp $in;
print &prime($in);
print "\n";
sub prime{
for($i=2;$i<($_[0]/2+1);$i++){
if($_[0]%$i ==0){return "not prime\n"}
}
return "prime\n";
}
Come on, that's the whole program, and half of it is I/O. It's so easy. Where does anyone get the idea that it's hard?
Nope.
perl:
print "enter a number: ";
$in = <>;
chomp $in;
print &prime($in);
print "\n";
sub prime{
for($i=2;$i<($_[0]/2+1);$i++){
if($_[0]%$i ==0){return "not prime\n"}
}
return "prime\n";
}
Come on, that's the whole program, and half of it is I/O. It's so easy. Where does anyone get the idea that it's hard?
Nope.
Originally posted by: DougK62
Originally posted by: xospec1alk
Originally posted by: b0mbrman
I don't know C++
I'm guessing the problem is more complicated than this but I had to do a program like this in some other language many years back...
X = number being tested
c = temp variable
For c = 2 to (X - 1)
if X = parse(X/c) then blah
c = c + 1
thats like a brute force way of doing it right? the class im taking, we're not allowed to brute force, besides with numbers like 19589 it mite take a while to get all the way up there
Uhh - that's the way you find a prime number. Can you think of an easier way? You have to check every (or at least most) numbers below a number to see if it's prime.
BTW, this is not "brute force" programming. Try google for the real definition.
well you don't have to check all numbers...
you can check 2, 3 and then only odd numbers (for example, and then try to perfectyour algorithm)
and anyway, even i you check all, you are not the one doing it the computer is...
and if you have a decent machine, this is really fast to do
specially in C++
Originally posted by: damiano
well you don't have to check all numbers... you can check 2, 3 and then only odd numbers (for example, and then try to perfectyour algorithm) and anyway, even i you check all, you are not the one doing it the computer is... and if you have a decent machine, this is really fast to do specially in C++Originally posted by: DougK62Uhh - that's the way you find a prime number. Can you think of an easier way? You have to check every (or at least most) numbers below a number to see if it's prime. BTW, this is not "brute force" programming. Try google for the real definition.Originally posted by: xospec1alkthats like a brute force way of doing it right? the class im taking, we're not allowed to brute force, besides with numbers like 19589 it mite take a while to get all the way up thereOriginally posted by: b0mbrman I don't know C++
It's not that slow for most values of N .... but unfortunately the primality algorithm only becomes non-trivial when you deal with large values of N (usually they compute 512 digit primes) .... i am assuming his instructor wants him to avoid a brute-force way because it has the potential to be very slow and wants his students to start assuming that computers can do EVERYTHING fast ... algorithms have to not only be correct but efficient.
Originally posted by: lukatmyshu
Originally posted by: damiano
well you don't have to check all numbers... you can check 2, 3 and then only odd numbers (for example, and then try to perfectyour algorithm) and anyway, even i you check all, you are not the one doing it the computer is... and if you have a decent machine, this is really fast to do specially in C++Originally posted by: DougK62Uhh - that's the way you find a prime number. Can you think of an easier way? You have to check every (or at least most) numbers below a number to see if it's prime. BTW, this is not "brute force" programming. Try google for the real definition.Originally posted by: xospec1alkthats like a brute force way of doing it right? the class im taking, we're not allowed to brute force, besides with numbers like 19589 it mite take a while to get all the way up thereOriginally posted by: b0mbrman I don't know C++
It's not that slow for most values of N .... but unfortunately the primality algorithm only becomes non-trivial when you deal with large values of N (usually they compute 512 digit primes) .... i am assuming his instructor wants him to avoid a brute-force way because it has the potential to be very slow and wants his students to start assuming that computers can do EVERYTHING fast ... algorithms have to not only be correct but efficient.
you are making a good point.
but for a college kid, he can start like this...
and then just work on making the algorith better...
removing all even numbers after trying to divide by two...and so on.
and then trying to use more complicated algorithms like you guys try to explain, but he couldn't even figure out the straight way to do it which is a simple loop.
oh well
the answer if you really want to find a better algorithm is always the same at the end: GOOGLE
This is getting pretty heated in here... is this for an introductory course in programming (1st semester, 2nd semester) or are we talking more advanced. That might help to make the distinction between doing raw number crunching or more elegant theorems and such.... also, what sort of numbers someone intends to input (I'd assume it's someone sitting at the keyboard typeing, which is unlikely to be more than 10 characters long).
I dunno ... when I was in High School we were always expected to do things as efficiently as possible. I remember having to use hash-tables to compute Fibonnaci sequences and what not ... at the same time, prime-testing does get pretty complex -- I'd still recommend using Fermat's Theorem .... it is the ONLY non-brute force way we have to guess the primality of a number and it's not that hard to code up .... maybe 3-4 lines max -- only because your instructor specifically asked for a non-brute force way. There were a lot of times in my years in CS classes where they expected you to find/derive a formula for something that wasn't intrinsically obvious. You have an answer ... go for it.
Right now this is the most efficient primality testing algorithm: PrimesInP.pdf
Go to page 4 and they give a simple algoritm to use.
Go to page 4 and they give a simple algoritm to use.
looks really cool actually..
but quite complex for a kid in his first or second C++ class in college
TRENDING THREADS
-
Discussion Zen 5 Speculation (EPYC Turin and Strix Point/Granite Ridge - Ryzen 9000)- Started by DisEnchantment
- Replies: 25K
-
Discussion Intel Meteor, Arrow, Lunar & Panther Lakes Discussion Threads
- Started by Tigerick
- Replies: 21K
-
Discussion Intel current and future Lakes & Rapids thread- Started by TheF34RChannel
- Replies: 23K
-
-
Facebook
Twitter