Programmierwettbewerb: Primzahlzerlegung

void Search2PrimFacts(i64 Number) {
  i64 i = 3; // naja, die zwei ist ja fast wirklich egal
  bool found = false;

  while ( i <= round(sqrt(Number)) && !found)
  {
     if (isPrime(i))
     {
        if (Number % i == 0)
        {
           printf("%I64d*%I64d=%i64d\n", i, Number / i, Number);
           found = true;
        }
     }
     i += 2;
  }
}

void Search2PrimFacts(i64 Number) {
  i64 i = 3, // naja, die zwei ist ja fast wirklich egal
      tmp; 
  
  tmp = round(sqrt(Number));

  while ( i <= tmp)
  {
     if (isPrime(i))
     {
        if (Number % i == 0)
        {
           printf("%I64d*%I64d=%i64d\n", i, Number / i, Number);
           [b]break; [/b]
        }
     }
     i += 2;
  }
}

for(i64 d = 2; d*d <= nr+1; d++)

bool IsPrime(i64 nr) {
  i64 tmp = ((i64)sqrt(nr))+1;
  
  for(i64 d = 2; d <= tmp; d++) {
    if (!(nr % d)) { 
      return false;
    }       
  }
  return true;
}

[b]long long[/b] number;
[...]
Search2PrimFacts(1949565409282837[b]LL[/b]);

#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#include <math.h>
#include <gmp.h>

bool IsPrime(mpz_t nr) {
	mpz_t d, tmp;
	
	mpz_init(d);
	mpz_init(tmp);
	mpz_set_ui(d, 2);
	mpz_pow_ui(tmp, d, 2);
	//printf("IsPrime\n");
	while(mpz_cmp(tmp, nr) <= 0) {
		//gmp_printf("d=%Zd, tmp=%Zd\n", d, tmp);
		if(mpz_divisible_p(nr, d))
			return false;
		mpz_add_ui(d, d, 1);
		mpz_pow_ui(tmp, d, 2);
	}
	return true;
}

void Search2PrimeFacts(mpz_t number) {
	mpz_t a, i, tmp;
	
	mpz_init(a);
	mpz_init(i);
	mpz_init(tmp);
	mpz_set_ui(i, 3);
	mpz_sqrt(tmp, number);
	
	while(mpz_cmp(i, tmp) <= 0) {
		if(mpz_divisible_p(number, i)) {
			if(IsPrime(i)) {
				mpz_cdiv_q(a, number, i);
				if(IsPrime(a)) {
					gmp_printf("%Zd * %Zd = %Zd\n", a, i, number); 
					break;
				}
			}
		}
		mpz_add_ui(i, i, 2);
	}
}

int main(void) {
	float millisecs;
	clock_t start, end;
	
	mpz_t number;
	
	mpz_init(number);
	
	mpz_set_str(number, "312133288776418481", 10);
	
	start = clock();     
	Search2PrimeFacts(number);
	end = clock();
	millisecs = (float)(end - start)/((float)CLOCKS_PER_SEC/1000);
	printf("Elapsed time in milliseconds: %f\n", millisecs);
	
	return 0;
}