نوشتن اعداد بر اساس حاصلضرب فاکتورهای اول آن

هر عددی را می توان بر اساس حاصلضرب مقسوم علیه های اول آن عدد نوشت . به مثالهای زیر توجه کنید :

589: 19 31
255700: 2 2 5 5 2557

می خواهیم برنامه ای بنویسیم که اعداد را از ورودی استاندارد یا از آرگومانهای فراهم شده در خط فرمان بخواند و مقسوم علیه های اول آن را پیدا کرده و خروجی به مانند بالا تولید کند . این برنامه عملیات دستور factor در سیستم های شبه یونیکس را پیاده می کند.

نکته مهم اینست که تابع find_next_prime که عدد اول بعدی را بر می گرداند علیرغم تلاش برای کاهش تعداد محاسبات هنوز کارآمد نیست . شما می توانید با داشتن دانش ریاضی و مطالعه الگوریتم های یافتن اعداد اول در اینترنت این تابع را بهینه سازی کنید .

#!/usr/local/bin/perl
#
# Mimic factor command in unix like systems :
# returns prime factors of any provided numbers
# on command line arguments or on standard input.
#
use strict;
use warnings;

# Global variable contain current prime number
# used by find_next_prime() function.
my $current_prime_number = 1;

# Find next prime number equal or greater that given number.
# Note this function is not efficient enoughly .  
sub find_next_prime {
	my $i = $current_prime_number + 1;
	my $prime;

	while (1) {
		# We assume that $i is prime number at beggining of the loop.
		$prime = 1;

		#
		# For test that a number is prime or not we must check for 
		# factors of that number in range of 2 .. sqrt(that number).
		# Obviously there are more efficient algorithmes too.
		#
		my $max = int (sqrt $i) + 1;

		# First we must find next prime number!
		for (my $j = 2; $j < $max; $j++) {
			if ($i % $j == 0) {
				# if $i % $j == 0 then $i is not prime then ...
				$prime = 0;
				last;
			}
		}
		if ($prime) {
			# $i is prime then update $current_prime_number
			$current_prime_number = $i;
			return $i;
		}

		$i++;
	}
}

sub find_factor {
	# Array to store prime factors to it.
	my @arr;
	# $number is the number we check for its prime factors.
	my $number = shift;

	# Reset $current_prime_number
	$current_prime_number = 1;
	while (1) {
		# find next prime number, it will bestored globally in $current_prime_number. 
		find_next_prime();
		# check $current_prime_number can divide $number ...
		while ($number % $current_prime_number == 0) {
			# if so push the $current_prime_number to array of calculated prime factors...
			push @arr, $current_prime_number;	
			# and update $number by dividing it to $current_prime_number.
			$number /= $current_prime_number;
		}

		# If the $number is 1 this is all done.
		last if $number == 1;
	}

	# Return the prime factors array.
	return @arr;
}

sub calc_and_print {
	my $number = shift;
	chomp $number;
	my @res = find_factor $number;
	print "$number: @res\n";
}

if (@ARGV) {
	# There is numbers provided as command line argumnets.
	while (my $c = shift) {
		calc_and_print $c;
	}
}
else {
	# No command line arguments. We must read from standard input.
	while(<STDIN>) {
		calc_and_print $_;
	}
}

نمونه استفاده از این برنامه را ببینید :

# perl fact.pl 500 9965 2588741
500: 2 2 5 5 5
9965: 5 1993
2588741: 1103 2347
# cat numbers
26541
98822214
23654141
# cat numbers | perl fact.pl
26541: 3 3 3 983
98822214: 2 3 3 3 23 251 317
23654141: 7 919 3677