Need help regarding divisible numbers 1

[johndoe3344]

How would I test whether a number is divisible by a certain combination of numbers (say 2 and 3?)

The number 4 fits, because it divides by 2, and then by 2.
The number 12 fits, because it divides by 3, then by 2 twice.
The number 15 doesn't fit because after dividing by 3, 5 is not divisible by 2 or 3 any further.

I would imagine the method has something to do with the modulus operator, but I can only see how to use the modulus operator to check if a number x is divisble by a number y.

if (x % y == 0) {
...}

Could anyone shed some light on this? Thanks.

 

[KevinADC]

Is this school/course work?

------------------------------------------
- Kevin, perl coder unexceptional!

 

[KevinADC]

You have started three other threads in the perl forum, and you have left them all hanging. The people that take the time to answer questions don't appreciate that.

------------------------------------------
- Kevin, perl coder unexceptional!

 

[johndoe3344]

No, this is not school/course work. I'm learning perl on my own, and I couldn't figure out a way to do this. I'm sorry about leaving the other threads hanging - I'll properly thank the people who help me and tell them that I solved my problem in the future.

 

[rharsh]

The number 12 fits, because it divides by 3, then by 2 twice.

Do you need to know how many times 2 goes into the result, or just that it is divisible by 2?

 

[johndoe3344]

Just that it's divisible by 2.

 

[MillerH]

Your problem is not clear.

Assuming you're just talking about divisibility:

If you're wanting to know if they are mutual factors, then you simply combine them into a single modulus statement. If you just want to know if they are both divisors, then you just use sequential modulus statements. However, given that 3 and 2 are mutual primes, you could actually use either method.

print [red]"[/red][purple]are mutually divisible[/purple][red]"[/red] [olive][b]if[/b][/olive] [red]([/red][fuchsia]12[/fuchsia] [blue]%[/blue] [fuchsia]2[/fuchsia][red])[/red] == [fuchsia]0[/fuchsia] && [red]([/red][fuchsia]12[/fuchsia] [blue]%[/blue] [fuchsia]3[/fuchsia][red])[/red] == [fuchsia]0[/fuchsia][red];[/red]
print [red]"[/red][purple]are mutual factors[/purple][red]"[/red] [olive][b]if[/b][/olive] [red]([/red][fuchsia]12[/fuchsia] [blue]%[/blue] [red]([/red][fuchsia]2[/fuchsia] [blue]*[/blue] [fuchsia]3[/fuchsia][red])[/red][red])[/red] == [fuchsia]0[/fuchsia]

[gray][i]# A better example would be 4 and 6[/i][/gray]
print [red]"[/red][purple]are mutually divisible[/purple][red]"[/red] [olive][b]if[/b][/olive] [red]([/red][fuchsia]12[/fuchsia] [blue]%[/blue] [fuchsia]4[/fuchsia][red])[/red] == [fuchsia]0[/fuchsia] && [red]([/red][fuchsia]12[/fuchsia] [blue]%[/blue] [fuchsia]6[/fuchsia][red])[/red] == [fuchsia]0[/fuchsia][red];[/red]
print [red]"[/red][purple]are mutual factors[/purple][red]"[/red] [olive][b]if[/b][/olive] [red]([/red][fuchsia]12[/fuchsia] [blue]%[/blue] [red]([/red][fuchsia]4[/fuchsia] [blue]*[/blue] [fuchsia]6[/fuchsia][red])[/red][red])[/red] == [fuchsia]0[/fuchsia]

Assuming you're talking about factorization:

Then just create a sub to remove all multiples of each factor.

[olive][b]sub[/b][/olive] [maroon]remove_factors[/maroon] [red]{[/red]
	[olive][b]my[/b][/olive] [blue]$number[/blue] = shift[red];[/red]
	[olive][b]for[/b][/olive] [olive][b]my[/b][/olive] [blue]$factor[/blue] [red]([/red][blue]@_[/blue][red])[/red] [red]{[/red]
		[olive][b]while[/b][/olive] [red]([/red][blue]$number[/blue] [blue]%[/blue] [blue]$factor[/blue] == [fuchsia]0[/fuchsia][red])[/red] [red]{[/red]
			[blue]$number[/blue] /= [blue]$factor[/blue][red];[/red]
		[red]}[/red]
	[red]}[/red]
	return [blue]$number[/blue][red];[/red]
[red]}[/red]

[olive][b]foreach[/b][/olive] [olive][b]my[/b][/olive] [blue]$number[/blue] [red]([/red][fuchsia]4[/fuchsia], [fuchsia]12[/fuchsia], [fuchsia]15[/fuchsia][red])[/red] [red]{[/red]
	print [red]"[/red][purple]the number [blue]$number[/blue] [/purple][red]"[/red][red];[/red]
	print [maroon]remove_factors[/maroon][red]([/red][blue]$number[/blue], [fuchsia]2[/fuchsia], [fuchsia]3[/fuchsia][red])[/red] == [fuchsia]1[/fuchsia] ? [red]"[/red][purple]fits[/purple][red]"[/red] : [red]"[/red][purple]doesn't fit[/purple][red]"[/red][red];[/red]
	print [red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
[red]}[/red]

Also, for personal amusement, I created two quick functions for calculating the gcd and lcm. I created a test script as well since you might want to expand the functionality to allow multiple numbers.

[olive][b]use[/b][/olive] [green]Test::More[/green][red];[/red]

[olive][b]use[/b][/olive] [green]strict[/green][red];[/red]

[gray][i]# Track test count for the "plan"[/i][/gray]
our [blue]$tests[/blue][red];[/red]
INIT [red]{[/red] [blue]$tests[/blue] = [fuchsia]0[/fuchsia] [red]}[/red]

[gray][i]####################################################################[/i][/gray]
[gray][i]# Test List[/i][/gray]

[gray][i]# Test Plan:[/i][/gray]
[gray][i]# The easiest way to test whether GCD and LCM are working correctly is[/i][/gray]
[gray][i]# work with numbers that are already factored.  That way you can easily[/i][/gray]
[gray][i]# see what the LCM and GCD should be.  We therefore start with a list of[/i][/gray]
[gray][i]# primes, and simply build numbers that we can then test for a solution.[/i][/gray]
[gray][i]#[/i][/gray]
[gray][i]# Also note that the Fibonaci Numbers have the unique property of making[/i][/gray]
[gray][i]# the Euclidian Algorithm take the most iterations.  Therefore it is[/i][/gray]
[gray][i]# useful to have such numbers included in your test data as boundary cases.[/i][/gray]

[gray][i]# List of primes. (Using Sieve of Eratosthenes)[/i][/gray]
[gray][i]#	my $number_max = 60;[/i][/gray]
[gray][i]#	my %isprime = map {$_ => 1} (2..$number_max);[/i][/gray]
[gray][i]#	for my $num (2..$number_max) {[/i][/gray]
[gray][i]#		if ($isprime{$num}) {[/i][/gray]
[gray][i]#			for (my $multiple = 2 * $num; $multiple <= $number_max; $multiple += $num) {[/i][/gray]
[gray][i]#				$isprime{$multiple} = 0;[/i][/gray]
[gray][i]#			}[/i][/gray]
[gray][i]#		}[/i][/gray]
[gray][i]#	}[/i][/gray]
[gray][i]#	print join ', ', sort {$a <=> $b} grep {$isprime{$_}} keys %isprime;[/i][/gray]
[gray][i]# 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59[/i][/gray]

[gray][i]# Fibonaci Numbers[/i][/gray]
[gray][i]#	my $fib_max = 100;[/i][/gray]
[gray][i]#	my @fib = (0, 1);[/i][/gray]
[gray][i]#	while ($fib[-1] < $fib_max) { push @fib, $fib[-1] + $fib[-2] }[/i][/gray]
[gray][i]#	print join ', ', @fib;[/i][/gray]
[gray][i]# 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144[/i][/gray]

[gray][i]# Mutual Primes[/i][/gray]
INIT [red]{[/red] [blue]$tests[/blue] += [fuchsia]10[/fuchsia] [blue]*[/blue] [fuchsia]2[/fuchsia][red]}[/red]
[olive][b]my[/b][/olive] [blue]@primes_mutual[/blue] = [red]([/red]
	[red][[/red][fuchsia]2[/fuchsia]**[fuchsia]2[/fuchsia] [blue]*[/blue] [fuchsia]3[/fuchsia], [fuchsia]5[/fuchsia] [blue]*[/blue] [fuchsia]7[/fuchsia][red]][/red],
	[red][[/red][fuchsia]3[/fuchsia]**[fuchsia]3[/fuchsia]    , [fuchsia]5[/fuchsia] [blue]*[/blue] [fuchsia]11[/fuchsia][red]][/red],
	[red][[/red][fuchsia]2[/fuchsia]**[fuchsia]5[/fuchsia]    , [fuchsia]41[/fuchsia][red]][/red],
	[red][[/red][fuchsia]7[/fuchsia]**[fuchsia]2[/fuchsia]    , [fuchsia]29[/fuchsia][red]][/red],
	[red][[/red][fuchsia]5[/fuchsia] [blue]*[/blue] [fuchsia]7[/fuchsia]   , [fuchsia]19[/fuchsia][red]][/red],
	[gray][i]# Fibonachi Numbers (Adjacent Numbers are Mutual Prime)[/i][/gray]
	[red][[/red][fuchsia]34[/fuchsia], [fuchsia]55[/fuchsia][red]][/red],
	[red][[/red][fuchsia]55[/fuchsia], [fuchsia]34[/fuchsia][red]][/red],
	[red][[/red][fuchsia]144[/fuchsia], [fuchsia]89[/fuchsia][red]][/red],
	[red][[/red][fuchsia]34[/fuchsia], [fuchsia]21[/fuchsia][red]][/red],
	[red][[/red][fuchsia]5[/fuchsia], [fuchsia]8[/fuchsia][red]][/red],
[red])[/red][red];[/red]
[olive][b]foreach[/b][/olive] [red]([/red][blue]@primes_mutual[/blue][red])[/red] [red]{[/red]
	[maroon]is[/maroon][red]([/red][maroon]gcd[/maroon][red]([/red][blue]@$_[/blue][red])[/red], [fuchsia]1[/fuchsia], [red]"[/red][purple]GCD (Mutual Primes)[/purple][red]"[/red][red])[/red][red];[/red]
	[maroon]is[/maroon][red]([/red][maroon]lcm[/maroon][red]([/red][blue]@$_[/blue][red])[/red], [blue]$_[/blue]->[red][[/red][fuchsia]0[/fuchsia][red]][/red] [blue]*[/blue] [blue]$_[/blue]->[red][[/red][fuchsia]1[/fuchsia][red]][/red], [red]"[/red][purple]LCM (Mutual Primes)[/purple][red]"[/red][red])[/red][red];[/red]
[red]}[/red]

[gray][i]# Other Numbers[/i][/gray]
INIT [red]{[/red] [blue]$tests[/blue] += [fuchsia]5[/fuchsia] [blue]*[/blue] [fuchsia]2[/fuchsia][red]}[/red]
[olive][b]my[/b][/olive] [blue]@numbers[/blue] = [red]([/red]
	[red][[/red][fuchsia]11[/fuchsia]    , [fuchsia]2[/fuchsia]**[fuchsia]2[/fuchsia] [blue]*[/blue] [fuchsia]3[/fuchsia], [fuchsia]5[/fuchsia] [blue]*[/blue] [fuchsia]7[/fuchsia][red]][/red],
	[red][[/red][fuchsia]2[/fuchsia]**[fuchsia]2[/fuchsia]  , [fuchsia]3[/fuchsia]**[fuchsia]3[/fuchsia]    , [fuchsia]5[/fuchsia] [blue]*[/blue] [fuchsia]11[/fuchsia][red]][/red],
	[red][[/red][fuchsia]3[/fuchsia]**[fuchsia]2[/fuchsia]  , [fuchsia]2[/fuchsia]**[fuchsia]5[/fuchsia]    , [fuchsia]41[/fuchsia][red]][/red],
	[red][[/red][fuchsia]13[/fuchsia]    , [fuchsia]7[/fuchsia]**[fuchsia]2[/fuchsia]    , [fuchsia]29[/fuchsia][red]][/red],
	[red][[/red][fuchsia]2[/fuchsia] [blue]*[/blue] [fuchsia]3[/fuchsia] , [fuchsia]5[/fuchsia] [blue]*[/blue] [fuchsia]7[/fuchsia]   , [fuchsia]19[/fuchsia][red]][/red],
[red])[/red][red];[/red]
[olive][b]foreach[/b][/olive] [red]([/red][blue]@numbers[/blue][red])[/red] [red]{[/red]
	[olive][b]my[/b][/olive] [red]([/red][blue]$gcd[/blue], [blue]$factor1[/blue], [blue]$factor2[/blue][red])[/red] = [blue]@$_[/blue][red];[/red]
	[olive][b]my[/b][/olive] [blue]$number1[/blue] = [blue]$gcd[/blue] [blue]*[/blue] [blue]$factor1[/blue][red];[/red]
	[olive][b]my[/b][/olive] [blue]$number2[/blue] = [blue]$gcd[/blue] [blue]*[/blue] [blue]$factor2[/blue][red];[/red]
	
	[maroon]is[/maroon][red]([/red][maroon]gcd[/maroon][red]([/red][blue]$number1[/blue], [blue]$number2[/blue][red])[/red], [blue]$gcd[/blue], [red]"[/red][purple]GCD[/purple][red]"[/red][red])[/red][red];[/red]
	[maroon]is[/maroon][red]([/red][maroon]lcm[/maroon][red]([/red][blue]$number1[/blue], [blue]$number2[/blue][red])[/red], [blue]$number1[/blue] [blue]*[/blue] [blue]$number2[/blue] / [blue]$gcd[/blue], [red]"[/red][purple]LCM[/purple][red]"[/red][red])[/red][red];[/red]
[red]}[/red]


[gray][i]####################################################################[/i][/gray]
[gray][i]# Test Plan[/i][/gray]

INIT [red]{[/red] plan [purple]tests[/purple] => [blue]$tests[/blue] [red]}[/red]

[gray][i]####################################################################[/i][/gray]
[gray][i]# The Functions[/i][/gray]

[gray][i]# Least Common Multiple[/i][/gray]
[olive][b]sub[/b][/olive] [maroon]lcm[/maroon] [red]{[/red] 
	die [red]"[/red][purple]Requires two positive numbers[/purple][red]"[/red] [olive][b]if[/b][/olive] [blue]@_[/blue] != [fuchsia]2[/fuchsia] || [blue]@_[/blue] != grep [red]{[/red][red]/[/red][purple]^[purple][b]\d[/b][/purple]+$[/purple][red]/[/red][red]}[/red] [blue]@_[/blue][red];[/red]
	return [blue]$_[/blue][red][[/red][fuchsia]0[/fuchsia][red]][/red] [blue]*[/blue] [blue]$_[/blue][red][[/red][fuchsia]1[/fuchsia][red]][/red] / [maroon]gcd[/maroon][red]([/red][blue]@_[/blue][red])[/red][red];[/red]
[red]}[/red]

[gray][i]# Greatest Common Divisor[/i][/gray]
[gray][i]# - Implemented using Euclidean Algorithm[/i][/gray]
[olive][b]sub[/b][/olive] [maroon]gcd[/maroon] [red]{[/red]
	die [red]"[/red][purple]Requires two positive numbers[/purple][red]"[/red] [olive][b]if[/b][/olive] [blue]@_[/blue] != [fuchsia]2[/fuchsia] || [blue]@_[/blue] != grep [red]{[/red][red]/[/red][purple]^[purple][b]\d[/b][/purple]+$[/purple][red]/[/red][red]}[/red] [blue]@_[/blue][red];[/red]
	
	[olive][b]my[/b][/olive] [blue]$remainder[/blue] = [blue]$_[/blue][red][[/red][fuchsia]0[/fuchsia][red]][/red] [blue]%[/blue] [blue]$_[/blue][red][[/red][fuchsia]1[/fuchsia][red]][/red][red];[/red]
	return [blue]$remainder[/blue] == [fuchsia]0[/fuchsia] ? [blue]$_[/blue][red][[/red][fuchsia]1[/fuchsia][red]][/red] : [maroon]gcd[/maroon][red]([/red][blue]$_[/blue][red][[/red][fuchsia]1[/fuchsia][red]][/red], [blue]$remainder[/blue][red])[/red][red];[/red]
[red]}[/red]

Anyway, that was an amusing diversion into number theory fun. Now back to real work.

- Miller

 

[johndoe3344]

Thank you very much Miller. I realized what I was missing now.

 

[feherke]

Hi

johndoe3344, if you found Miller's code helpful, then please click the

* [navy]Thank MillerH
for this valuable post![/navy]

link then click again to confirm in the pop-up window which will appear.

That is the proper way to thank for the received help on Tek-Tips.

Feherke.

http://rootshell.be/~feherke/