[c++] Finding prime factors

[Stiltzkin]

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.

#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? 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?

[slimsam1]

Hello, world.

Use the [code] tags to format it nicely.

[vinaur]

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

[Stiltzkin]

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

[Yakk]

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.

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?

[Rangsk]

I made a fun version of this.

#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.

[Lebell]

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



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

;*****************************************************************************************
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,DSATASEG,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

[Rekna]

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

[Stiltzkin]

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

[Rekna]

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.

#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;
}

[pixelbend]

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.

[Yakk]

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. . .

[archpaladin]

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

[bendsley]

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

#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.

[n0nsensical]

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.