Beginners Task #2

[Zen]

cout << "Your number is a 0, 1, or 2. These cannot be prime."<< endl;

Not true. 2 is prime. [safety net]as far as I know[/safety net]

Sorry for the unconstructive criticism, I just had to...

[merlinfire]

If someone is gonna put in 2 to check it for prime I might as well entertain their delusion.


Edit:It should actually read that they cannot be 'checked' for prime. Which is also not totally true....ARGH! You got me, lol. To be honest, I was a little more worried about getting the code right. Math functions don't come easy to me, I made my lowest ACT score in math.

[Zen]

[chewing the rag]
Sure, but it's still prime

Again, sorry for the spam

[merlinfire]

Also, if you see any small stylistic errors, please don't just assume its my style. I'm a n00b! Most of the time weird style is done out of ignorance on my part. Please correct me at every turn.

[schloob]

anyways, comments just arent my style :-\

They'll get to be.

you wish :-]

Hey, leave shloob alone. Someone that never wishes to be a professional programmer as shloob obviously doesn't has no need to learn proper coding techniques. Many people stay beginners and hacks, leaves the big money to us pros.

exactly

im not following the shloob though -.- what kind of scam is this

[Alvaro]

Code: Select all

#include <iostream>
#include <vector>

// Finds the factors of n and returns them as a vector
std::vector<unsigned> factors(unsigned n){
  std::vector<unsigned> f;
 
  // Take care of some trivial cases first
  if(n<4){
    f.push_back(n);
    return f;
  }
 
  // Try to divide by all numbers until sqrt(n) is reached
  for(unsigned k=2;k*k<=n;++k){
    // Extract as many factors k as we can
    while(n%k==0){
      f.push_back(k);
      n/=k;
    }
  }
 
  // If at the end n still has something in it, it must be prime, so just add it.
  if(n>1)
    f.push_back(n);
 
  return f;
}

void print_vector(std::ostream &os, const std::vector<unsigned> &v, const char *sep){
  if(v.size()==0)
    return;
  os << v[0];
  for(size_t i=1;i<v.size();++i)
    os << sep << v[i];
}

int main(){
  std::cout << "Enter a number: " << std::flush;
  unsigned n;
  std::cin >> n;
 
  std::cout << n << " = ";
  print_vector(std::cout, factors(n)," x ");
  std::cout << std::endl;
}



I have code that allows you to print the factors using `std::cout << separator(" x ") << factors(n) << std::endl;', but it was a little complicated and I don't want to scare any beginners.

Note that you don't have to check each factor you find for primality: the smallest factor of an integer is always prime (easy theorem). You can speed up the algorithm by only trying to divide by 2 and then odd numbers, or by 2, 3 and multiplies of 6 plus or minus 1. I left that out to keep things simple.

[Alvaro]

Here is an alternative:

Code: Select all

#include<iostream>
using namespace std;
int main(){cout<<"Enter a number: "<<flush;unsigned o=2,o_;cin>>o_;cout
<<o_;char O[]=" = ";if(o_<4)return cout<<O<<o_<<'\n',0;for(;o_>=o*o;++o
)for(;o_%o==0;cout<<O<<o,1[O]='x')o_/=o;o_>1&&cout<<O<<o_;cout<<'\n';}

[Guest]

Note that you don't have to check each factor you find for primality: the smallest factor of an integer is always prime (easy theorem). You can speed up the algorithm by only trying to divide by 2 and then odd numbers, or by 2, 3 and multiplies of 6 plus or minus 1. I left that out to keep things simple.

I am not sure exactly what you mean, and if I can explain a little more. My attempt does need some help.

[Alvaro]

I'll try to explain with an example, n=150.

I look for factors of 150, starting with 2. I divide 150 by 2 as many times as I can (once). So I can already write "2 x ", and what follows will be a factorization of 75. In my algorithm, I destroy the old value of n as I go, taking out all the factors that I have found so far.

Now n=75, and I have to look for factors. I don't have to try 2 again, because I already extracted as much as I could. So I try with 3. So I now have "2 x 3 x ", and now I have to factorize 25.

n=25, and I don't have to try 2 or 3. I try 4, although there is no need, because 4 is not prime, which means that we already know that you can't divide 25 by 4 (otherwise 25 would be divisible by some prime smaller than 4, which we have already rooted out). Then I try 5, and I see that it divides twice. Now I have "2 x 3 x 5 x 5" and the factorization is over, because n=1.

If the largest factor only appears once, then the loop will be aborted when it is clear that the remaining n is prime, so we have to print it.

Wow! So much explaining for such a small function. I probably didn't explain it very well, though.

[Bladesniper]

Here is an alternative:

Code: Select all

#include<iostream>
using namespace std;
int main(){cout<<"Enter a number: "<<flush;unsigned o=2,o_;cin>>o_;cout
<<o_;char O[]=" = ";if(o_<4)return cout<<O<<o_<<'\n',0;for(;o_>=o*o;++o
)for(;o_%o==0;cout<<O<<o,1[O]='x')o_/=o;o_>1&&cout<<O<<o_;cout<<'\n';}

lol. Alvaro is spamming the forums!

[merlinfire]

I understand what you mean Alvaro. I didn't think of that.....after all math is my weak point. I'm sure that is going to haunt me in this field....

[Guest]

Thank you Alvaro for taking the time to explain that. I am going to digest that and then post a updated version.

[Guest]

This is the updated version.

Code: Select all

#include <iostream>
using namespace std;

long primenext(long* prime);

int main()
{
   for(;;)
   {
      
      int answer;
      cout << endl;
      cout << "Enter a number for Prime Factors : " << endl;
      cin >> answer;
      long prime = 2;
      long factor = 0;
      if (answer > 0)
      {
         do
         {
            if (answer % prime == 0)
            {
               factor = answer / prime;
               if (answer == prime)//the end if they are ==
                  answer = 0;
               else
                  answer = factor;
               cout << prime << ((0 == answer) ? "." : "x");
            }
            else                     
            {
               //next++ will decide the array number
               primenext(&prime);//get next prime
            }
         }while(answer > 0);
      }
      else
      {
         cout << "That was out of range." << endl;
         return 0; //check for valid input
      }
   }
}

long primenext(long* prime) //prime number generator
{
   if(*prime == 2)// New and improved
      *prime = 3;
   else
   {
      *prime += 2;
   }
      return *prime;
}

Thanks to Alvaro explanation of finding prime numbers and prime factors
with that insight I fixed my code.

Thank you very much Alvaro.

[RaH]

I am stuck, I have no clue how to set up this task. Yes I have thought about looking at some of the other posts, but I would be too tempted to cheat and copy someones code. Anyone know of a website that descripbes, how to perfom math in C++? And before the flames roll on in, yes I have looked inside math.h and it says nothing about primes.

Here is what I have so far:

Code: Select all

#include <iostream>
using namespace std;

int main()
{
     int UserNum;
     cout << "Will break a number down into it's prime factors\n";
     cout << "Enter your number: \n";
     cin >> UserNum;

     if(RaH == STUMPED)
     {
           cout << "Insert clue here\n";
      }
      return 0;
}


IGNore this I just read Alvro's previous.[.b]

[Guest]

Note that you don't have to check each factor you find for primality: the smallest factor of an integer is always prime (easy theorem). You can speed up the algorithm by only trying to divide by 2 and then odd numbers, or by 2, 3 and multiplies of 6 plus or minus 1. I left that out to keep things simple.

This should help if you did not already see it.

I'll try to explain with an example, n=150.

I look for factors of 150, starting with 2. I divide 150 by 2 as many times as I can (once). So I can already write "2 x ", and what follows will be a factorization of 75. In my algorithm, I destroy the old value of n as I go, taking out all the factors that I have found so far.

Now n=75, and I have to look for factors. I don't have to try 2 again, because I already extracted as much as I could. So I try with 3. So I now have "2 x 3 x ", and now I have to factorize 25.

n=25, and I don't have to try 2 or 3. I try 4, although there is no need, because 4 is not prime, which means that we already know that you can't divide 25 by 4 (otherwise 25 would be divisible by some prime smaller than 4, which we have already rooted out). Then I try 5, and I see that it divides twice. Now I have "2 x 3 x 5 x 5" and the factorization is over, because n=1.

If the largest factor only appears once, then the loop will be aborted when it is clear that the remaining n is prime, so we have to print it.

Wow! So much explaining for such a small function. I probably didn't explain it very well, though.