Премьер-факторизации чисел до 1000


Я читала математики: очень короткое введение , и это отметил премьер-факторизации. Будучи любопытным человеком, я должен написать свою реализацию на Perl.

Эта программа выводит простые множители чисел между 0 и 1001.

Я не люблю перечислять все мои подпрограммы, прежде чем все остальное, но я не уверен, что будет лучшей альтернативой.

Также, я помню, где-то не брутфорс способ узнать, является ли число является простым. У кого-нибудь есть идеи? Я-начинающий/средний программист Perl и будем признательны за предложения по улучшению моей техники.

#!/usr/bin/perl
use strict;
use warnings;
use 5.010;

#This array will contian the results of the factorization
our @result;

sub factorize {
  my($num,$factorsRef) = @_;

  # If the only factor is 1, it is a prime number
  # return the number itself since primes don't
  # factorize in the known universe
  if(${$factorsRef}[0] == 1) {
    push @result, $num;
    return;
  }


  if($num % ${$factorsRef}[0] == 0) {
    push @result, ${$factorsRef}[0];
    my $divResult = $num/${$factorsRef}[0];

    # If the result of the division is a prime
    # we have reached the end of the process
    if(isPrime($divResult)) {
      push @result, ($divResult);

    # If it is not a prime, go down to the
    # next level
    } else {
      factorize($divResult,$factorsRef);
    }

  # If the number is no longer divisible by the
  # current factor, take the factor out so that
  # the function can use te next factor
  } else {
    shift @{$factorsRef};
    factorize($num,$factorsRef);
  }
}

sub getPrimeFactors {
  my $num = shift;
  my $counter = 1;
  my @primeFactors;

  if(isPrime($num)) {
    push @primeFactors, 1;
    return \@primeFactors;
  }

  while($counter++ <= ($num / 2)) {
    next unless $num % $counter == 0;
    push @primeFactors, $counter if(isPrime($counter));
  }
  return \@primeFactors;
}

sub isPrime {
  my $num = shift;
  my $limit = $num/2;
  for(my $i=2; $i<=$limit ;$i++) {
    if ($num%$i == 0) { return 0;}
  }
  return 1;
}

sub printResults {
  my $num = shift;
  print $num . ' = ' . shift @result;
  print " x $_" for @result;
  print "\n";
}

# Where everything happens
for(1..1000) {
  my $num = $_;
  factorize($num,getPrimeFactors($num));
  printResults($num);

  @result = ();
}

Пример вывода:

983 = 983
984 = 2 x 2 x 2 x 3 x 41
985 = 5 x 197
986 = 2 x 17 x 29
987 = 3 x 7 x 47
988 = 2 x 2 x 13 x 19
989 = 23 x 43
990 = 2 x 3 x 3 x 5 x 11
991 = 991
992 = 2 x 2 x 2 x 2 x 2 x 31
993 = 3 x 331
994 = 2 x 7 x 71
995 = 5 x 199
996 = 2 x 2 x 3 x 83
997 = 997
998 = 2 x 499
999 = 3 x 3 x 3 x 37
1000 = 2 x 2 x 2 x 5 x 5 x 5


907
2
задан 7 июня 2011 в 09:06 Источник Поделиться
Комментарии
1 ответ

Есть несколько вещей, которые могут улучшить эту логику:


  • Для того, чтобы узнать, является ли число п простым, нужно только подойти к кв. корень(N), не н/2; который ускорит премьер-проверки существенно для больших чисел.

  • Также, если вы проверяете, является ли последовательность чисел являются простыми, вы должны хранить предыдущие результаты вместо того, чтобы начинать с нуля все время. Функция, приведенная ниже, вычисляет простые числа от 2-1000, который является хорошей "предварительной обработки" шаг за вашей функции (разложение на множители-это уже вопрос обходе только, что простые числа список)

Вычислить простые числа от 1..1000:

use strict;

my @primes;
my $i;

for my $i (2..1000) {
my $isPrime = 1;
my $sqrt = int(sqrt($i));
for my $j (@primes) {
if (($i % $j) == 0) {
$isPrime = 0;
last;
}
last if $j > $sqrt;
}
if ($isPrime) {
push @primes, $i;
}
}

print join(", ", @primes);

4
ответ дан 8 июня 2011 в 05:06 Источник Поделиться