Tilted Forum Project Discussion Community - [c++] Finding prime factors

- Tilted Technology (https://thetfp.com/tfp/tilted-technology/)

- - [c++] Finding prime factors (https://thetfp.com/tfp/tilted-technology/84070-c-finding-prime-factors.html)

[c++] Finding prime factors

Am I allowed to show off in this board?
For the record, I taught myself VB and C++. ASP is also just VB+HTML... well anyway... I have a friend who's doing mechanical engineering and as part of his curriculum he has to take these online C++ courses. He's fairly clueless when it comes to actual programming, even though he's a genius when comes to pure mathematics. So he asked me if I could write him a program that would take an input and output it's prime factors. Now, I did it in under an hour, and I am quite proud of what I did because the last time I touched C++ was highschool, which was at least two years ago.

Code:

#include <stdio.h>



int find_primes();

int primes[20], num;



int main()

{

        printf("input a number:");

        scanf("%d", &num);

        if(num == 0)

                printf("0 does not have any prime factors");

        else if(num == 1)

                printf("1 only has a prime factor of itself");

        else

                find_primes();

        printf("%d's primes are:\n", num);

        for(int i = 0; i < 20; i++)

                printf("%d\n", primes[i]);

        scanf("%d", &num);

}



int find_primes()

{

        int finished = 0, bucket = num, i, last_prime=0, one_found=0, entered_loop = 0;

        do

        {

                entered_loop = 0;

                for(i = 2; i <= int(bucket / 2); i++)

                {

                        entered_loop = 1; // tell it that it did enter the loop

                        one_found = 0; // it's the beginning of the loop, so it hasn't

                                                   // found anything yet. one_found = 0;

                        if(bucket % i == 0) // if it divides nicely

                        {

                                primes[last_prime] = i; // toss it into the array of primes

                                last_prime++; // be ready if another prime is found

                                one_found = 1; // tell it that a prime was found

                                bucket = bucket / i; // hard to explain. just figure it out

                        }

                        if(one_found == 1)

                                break; // exit the for loop and go back into the do ... while loop

                }

                if(one_found == 0 || entered_loop == 0) // if the for ... loop failed to find a prime in the

                {                                           // or it failed to enter the loop, then just stop

                        finished = 1;

                        primes[last_prime] = bucket; // figure this one out too

                }

        } while(finished == 0);

}

Now, I know this isn't the most elegant solution possible, but hey, I think it's pretty darn good considering the circumstances. Oh, and might I add that I was studying biology while programming this? :D BTW I'm majoring in pharmacy, which has nothing to do with programming. All right, I'm done blowing my own horn (I hate that expression). I guess... show us some of your exploits?

Code:

Hello, world.

Use the [code] tags to format it nicely.

That doesn't look too much like C++ to me. More like C. Good job for someone who hasn't programmed for a while.

Thanks for the tip Slimsam1.

You're right, it's not C++ since I didn't use any classes. It's been so long that I didn't even remember the distinction between C and C++ until you pointed it out Vinaur :thumbsup:

Laugh, that is C code. =)

A quick way to find prime factors is as follows:
1> Find all prime numbers up to sqrt(x).
To find all prime numbers up to sqrt(x):
+Try to factor numbers up to sqrt(x). Those with 1 factor are prime.

You do the above dynamically. To save on work, you only check numbers equal to 1 and 5 mod 6 for primeness.

Code:

enum {max_primes = 10000};

typedef int prime_list[max_primes];

struct {

  prime_list primes;

  int high_water_mark;

  int found_primes;

  bool sorted;

} primes;



primes make_seed_primes() {

  primes retval = {0};

  prime_list tmp = {2, 3, 5, 7, 11, 13, 17};

  retval.primes = tmp;

  retval.high_water_mark = 17;

  retval.found_primes = 7;

  retval.sorted = true;

  return retval;

}



int find_factor( primes* known_primes, int value, bool* error );

bool extend_primes( primes* known_primes, int value, bool* error );

bool find_prime( primes* known_primes, int value, bool* error );



bool is_prime( primes* known_primes, int value, bool* error ) {

  if (!error) return false;

  if (!known_primes) *error = true

  if (!*error) return false;



  if (value < known_primes->high_water_mark) {

    return find_prime( known_primes, value, error );

  }



  if (value > known_primes->high_water_mark * known_primes->high_water_mark) {

    extend_primes( primes, sqrt(value), error );

  }



  return find_factor(primes, value, error)

}



int find_factor( primes* known_primes, int value, bool* error ) {

  if (!error) return false;

  if (!known_primes) *error = true

  if (!*error) return false;



  if (value == 0) return 0;

  if (value == 1) return 0;



  {for (int i = 0; i < known_primes.found_primes; ++i) {

    if (value % i == 0) return i;

  }}

  return 0;

}



void extend_primes( primes* known_primes, int value, bool* error ) {

  if (!error) return false;

  if (!known_primes) *error = true

  if (!*error) return false;



  {for (int i = known_primes->high_water_mark; i < value; ++i ) {

    if (is_prime(known_primes, i, error) {

      int old_max = known_primes->primes[known_primes->found_primes-1];

      int& new_max = known_primes->primes[known_primes->found_primes++];

      new_max = i;

      if (new_max < old_max) known_primes->sorted = false;

    }

  }}

}



bool find_prime( primes* known_primes, int value, bool* error ) {

  if (!error) return false;

  if (!known_primes) *error = true

  if (!*error) return false;



  if (!known_primes->sorted) {

    assert(false);  // this code is just here for paranoia.  Then again, maybe I'm wrong, and it is needed.

    std::sort(&(known_primes->primes[0]), &(known_primes->primes[0])+known_primes->found_primes);

    known_primes->sorted = true;

  }



  return std::binary_search(&(known_primes->primes[0]), &(known_primes->primes[0])+known_primes->found_primes, value)

}



enum {max_factors = 100}

typedef int factors[max_factors] factors;



struct {

   factors nums;

   int count;

} factor_list;



// returns the non-unitary factors of value.  known_primes is optional.

factor_list factor(int value, primes* known_primes = 0) {

  primes tmp = {0};

  if (!known_primes) {

    known_primes = &tmp;

  }

  if (known_primes->high_water_mark < 17) {

    *known_primes = make_seed_primes();

  }

  

  bool error = false;

  factor_list retval = {0};



  if (value < 0) value *= -1;

  if (value <= 1) return retval;



  int v = value;

  while (true) {

    f = find_factor(known_primes, v, &error );

    if (f == 0) break;

    if (error) break;

    assert(v%f ==0);

    retval.nums[retval.count++] = f;

    v /= f;

  }



  assert(!error);

  return retval;

}

missing:
I avoided using std::vector's, because newbies find those confusing.
I didn't check array size limits.
I never compiled the above.
Error handling is minimal. It shouldn't crash.

Anyone see any mistakes?

I made a fun version of this.

Code:

#include <iostream>

#include <string>

#include <sstream>

#include <vector>



using namespace std;



void factor(int, vector<int>&);



int main(int argc, const char* argv[])

{

  // Check the number of parameters

  if (argc != 2)

  {

    cout << "Usage: " << argv[0] << " number_to_factor" << endl;

    return 0;

  }

  

  // Convert the parameter to an integer

  stringstream n_stream;

  int n;

  n_stream << argv[1];

  if (!(n_stream >> n)) {

    cout << "Invalid integer: " << argv[1] << endl;

    return 0;  

  }

  

  vector<int> primes;

  

  // Factor the number

  factor(n, primes);

  cout << endl;

  return 0;

}



void factor(int n, vector<int> &primes)

{

  if (n < 2)

    return;

  

  for (vector<int>::iterator i = primes.begin(); i != primes.end(); i++)

  {

    int p = *i;

    if (n % p == 0) {

      cout << p << " ";

      factor(n / p, primes);

      return;

    }

  }

  

  int new_p = (primes.size() > 0) ? primes.back() : 2;

  while (n % new_p != 0)

    new_p++;

  primes.push_back(new_p);

  cout << new_p << " ";

  factor(n / new_p, primes);

}

Yes, this can be made into a loop very easily, but where's the fun in that?

An interesting aside: It displays the complete prime factorization (with prime repeats), but the primes vector now contains only the unique primes that divide the number.

Just for giggles and grins, here's the same thing in assembler.

:D

----------------------------------------------------------------

Quote:

;*****************************************************************************************
STACK SEGMENT PARA STACK 'Stack'
DW 32 DUP(0)
STACK ENDS
;*****************************************************************************************
DATASEG SEGMENT PARA 'Data'

NUMA DB 40 ;first number in range to check
NUMB DB 65 ;last number in range to check
CNT1 DB 0 ;loop counter 1
CNT2 DB 0 ;loop counter 2
PCNT DB 0 ;'prime' counter for prime numbers found
PFLAG DB ? ;'prime' flag to signal that a prime number has been found
PTBL DB 14 DUP (0) ; table to store prime numbers
DISPA DB 'Number A = ','$'
DISPB DB 'Number B = ','$'
DISPNO DB 'Number of Primes found: ','$'
DISPPRIME DB 'The Prime numbers between them are: ','$'

NEGSIGN DB '

ASCVAL DB 5 DUP (' '), '$'

DATASEG ENDS
;*****************************************************************************************
CODESEG SEGMENT PARA 'Code'
MAIN PROC FAR
ASSUME SS:STACK,DS:DATASEG,CS:CODESEG ;assign the stack,data and code pointers
MOV AX,DATASEG ;Set the address of the
MOV DS,AX ; segment into DS (boiler plate)

MOV BH,NUMA ;initialize BH as the outer loop counter which will be ;the number to be tested for prime
;begin outer loop
L10: ;begin outer loop, from NUMA to NUMB
MOV PFLAG, 1 ;initialize the 'prime' flag to true

CMP BH,NUMB ;test for exit outer loop, is the counter > number B?
JG L40 ;if it is, then exit from outer loop and testing

;begin inner loop
MOV BL,2 ;begin inner loop, from 2 to 1/2 of number being tested
L20:
MOV AX,BH
IDIV BL ;divide the number, in BH, by the current counter value
CMP AH,00 ;test for a remainder
JNE L25 ;if there is a remainder, jump to the end of loop test
;and do NOT set the 'prime' flag to false
MOV PFLAG, 0 ;otherwise, set the 'prime' flag to false and
JMP L30 ;exit the inner loop

L25:
MOV AH,BH
SHR AH,1 ;shift right effectively divides AH by 2, dropping any remainder
CMP BL, AH ;test end of inner loop, is the loop counter, BL, > 1/2 the value of
; the number being tested (the outer loop counter)?
JG L30 ;if so, then exitout of inner loop
INC BL ;increment the inner loop counter by 1
JMP L20 ;end inner loop, jump back to beginning at L20
;end inner loop
;test for prime flag
L30:
CMP PFLAG,1 ;check the 'prime' flag. If it's still true, then store the number
JNE L35 ;jump to L35 if not true
MOV PTBL + PCNT, BH ;else, store the number in PTBL
INC PCNT ;and increment the 'prime' counter

L35:
INC BH ;increment the outer loop counter by 1
JMP L10 ;end outer loop, jump back to beginning at L10
;end outer loop

;end of testing logic
;begin printing results code

L40:

MOV AH,09H ;request for display
LEA DX, DISPA ; for display A label
INT 21H

CALL CONVERT
MOV AH,09H
LEA DX,ASCVAL

MOV AX,4C00H ; end
INT 21H ; processing

MAIN ENDP
;--------------------------------------------------------------------------------------------------
; This procedure converts a hex based number into an ASCII value
; for display purposes

CONVERT PROC NEAR
MOV CX,10
MOV AX,HVAL
LEA SI,ASCVAL ; load the first position into SI

B20: ; added - this part can do a negative
CMP AX, 0 ; test if neg
JGE B25 ; if >=0, then jump to normal processing
NEG AX ; twos comp the AX register if it is zero to get the pos equ

MOV [SI],'-' ; put a negative sign there

B25: ADD SI, 4

CMP AX, CX
JB B30

XOR DX, DX
DIV CX

OR DL,30H
MOV [SI],DL

DEC SI
JMP B20

B30:
OR AL,30H
MOV [SI],AL

RET

CONVERT ENDP
;---------------------------------------------------------------------------------------------------
; This procedure displays one character to the screen.

DISPLAY PROC NEAR
PUSHA ; preserve registers
LEA DX, ASCVAL
MOV AH,09H
INT 21H
POPA
RET
DISPLAY ENDP

;---------------------------------------------------------------------------------------------------
CODESEG ENDS
END MAIN

Ahh assembly! Brings back the good old days during my undergrad where I programmed frogger in assembly ;)

Somehow, I still like mine best since it is the shortest, and it never fails.

A couple optimizations for you stiltzkin

when you find a prime remove as many of that prime as possible from the list then start searching at that number plus 2, don't start back at 2. Also don't increment i by one instead increament it by 2 (making sure it is odd to start).

Here is what I came up with in 3 minutes. I don't actually save the primes but one could easily add the code to save them in a few minutes.

Code:

#include <iostream>

using namespace std;



int main()

{

        unsigned  int n;

        cout << "Enter a positive number: ";

        cin >> n;

        cout << "The prime factors are:\n1 ";



        //remove 2's

        while(n%2==0)

        {

                cout << "2 ";

                n/=2;

        }

        int p=3;

        //remove odd numbers

        while(n!=1)

        {

                while(n%p==0)

                {

                        cout << p << " ";

                        n/=p;

                }

                p+=2;

        }

        cout << endl;

}

Sieve of Eratosthenes

The Sieve of Eratosthenes is your friend when it comes to primes

http://ccins.camosun.bc.ca/~jbritton/jberatosthenes.htm

Lebell - an evil genius! Assembly is one of those things I've always been aware of, but just a little too scared to try myself.

Quote:

Originally Posted by pixelbend

The Sieve of Eratosthenes is your friend when it comes to primes

http://ccins.camosun.bc.ca/~jbritton/jberatosthenes.htm

Ik, order(n) memory requirements.

Admittedly, mine is order n/lg(n). And you could maybe RunLengthEncode the Sieve data structure to make it use less memory. . .

Now just let the programs run on numbers on the order of 1024-bits and you'll be a codebreaker.....

I'll see your 49 line program Stiltzkin, and raise you a 43 line variant.

Quote:

#include <iostream.h>
#include <bool.h>
#include <math.h>

bool IsPrime(int num); // function prototype

int main( )
{ int first, last;

cout << "find primes between what two numbers: ";
cin >> first >> last;

int k; // variables can be declared anywhere in block
for (k = first; k <= last; k++)
{
if (IsPrime (k))
cout << k << endl;
}
return 0;
}

bool IsPrime (int num)
// precondition: num >=2
// postcondition: returns 1 if num is prime, else 0
{
if (num == 2) // the only even prime
return true;
else if (num % 2 == 0) // other even numbers are composite
return false;
else
{
bool prime = true;
int divisor = 3;
int upperLimit = static_cast<int>(sqrt(num) + 1);
while (divisor <= upperLimit)
{
if (num % divisor == 0)
prime = false;
divisor +=2;
}
return prime;
}
}

note: I don't have a compiler on this machine, so I'm running this in my head. It should work.

Just because it doesn't use classes doesn't mean it's not C++. As Bjarne Stroustrup would tell you, C++ is a multiparadigm programming language, which includes procedural programming like C and object oriented programming. That said, the original code was still closer to C since it used only the C library.