Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 a special function listing all the factors of an integer
Index -> Programming, Turing -> Turing Help
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Tricia




PostPosted: Fri Oct 01, 2004 8:35 pm   Post subject: a special function listing all the factors of an integer

is there any special function or command or statement for that?
Sponsor
Sponsor
Sponsor
sponsor
Paul




PostPosted: Fri Oct 01, 2004 9:07 pm   Post subject: (No subject)

I don't think so... I think you'll have to find out the factors normally through running a loop to that number... Um I'm rusty, but I'll try:

code:

var num: int
put "Input integer: "..
get num
for a: 1..num %runs loop from 1 to the integer
if strintok(realstr(num/a,0)) then %checks if num/a is integer or not
%so if u enter 5, 5/1 = 5, thats a factor, 5/2 is 2.5, which is not
%an integer, so not factor.
put a, " "..
end if
end for


there's prolly lots of stuff I didn't think of, but its too late, can't think.
wtd




PostPosted: Fri Oct 01, 2004 10:41 pm   Post subject: (No subject)

First, we'll define a function to determine if a number is prime. Prime numbers are divisible only by themselves and one.

To find if a number is prime, we'll count up from two to one less than the original number. If the number is evenly divisible by any of these, then it can't be prime. If it goes all the way through without this happening, we know the number is prime.

code:
function prime(n : int) : boolean
   for c : 2 .. (n - 1)
      if (n mod c) = 0 then
         result false
      end if
   end for

   result true
end prime


We can now use this function to make sure the factors we find are prime.

Now, we'll create a function which finds the smallest factor of a given number.

First we check to see if the number is a prime number. If it is, then we can't factor it, and there's no point trying. We can just return that number.

If it's not a prime, we'll again count up, and as soon as we find a factor, we'll return that. We will find a factor before the end of the loop.

code:
function findSmallestFactor(n : int) : int
   if prime(n) then
      result n
   else
      for c : 2 .. (n - 1)
         if (n mod c) = 0 then
            result c
         end if
      end for
   end if     
end findSmallestFactor


Now, to put it all together. We'll start out with a number. We have a loop. Each time around we find the smallest factor of that number. If the smallest factor is the number, then we exit the loop. Otherwise we print the smallest factor, divide the number by the factor we found and start the loop all over.

code:
procedure printFactors(var n : int)
   loop
      var smallestFactor : int := findSmallestFactor(n)
     
      if smallestFactor = n then
         exit
      else
         put smallestFactor
         n /= smallestFactor
         % equivalent to:
         % n := n / smallestFactor
      end if
   end loop
end printFactors


Any questions?
Paul




PostPosted: Fri Oct 01, 2004 11:05 pm   Post subject: (No subject)

uh... so I was wrong then?
wtd




PostPosted: Fri Oct 01, 2004 11:08 pm   Post subject: (No subject)

I can't test it to see if it works. However, I prefer to use math. Munging things back and forth from numbers to strings just feels wrong if it can be done another way. Smile
Cervantes




PostPosted: Sat Oct 02, 2004 6:54 am   Post subject: (No subject)

Pauls works, its just a little indirect.
instead of using strintok and realstr and such you could just use mod
code:

var num : int
put "Input integer: " ..
get num
for i : 1 .. num
    if num mod i = 0 then
        put i, "  " ..
    end if
end for
wtd




PostPosted: Sat Oct 02, 2004 12:31 pm   Post subject: (No subject)

Cervantes wrote:
Pauls works, its just a little indirect.
instead of using strintok and realstr and such you could just use mod
code:

var num : int
put "Input integer: " ..
get num
for i : 1 .. num
    if num mod i = 0 then
        put i, "  " ..
    end if
end for


The only problem with this approach is that you won't get prime factors of an integer. Say you start with 64. You'll get:

1
2
4
8
16
32
64

Only two of those numbers are primes, and 1 and 64 can be elided since 1 and itself are always factors of a number.
Paul




PostPosted: Sat Oct 02, 2004 3:41 pm   Post subject: (No subject)

well... he asked for factors, I never thought about prime factors.
Sponsor
Sponsor
Sponsor
sponsor
wtd




PostPosted: Sat Oct 02, 2004 4:33 pm   Post subject: (No subject)

What can I say... I am (or at least was) a math geek. Smile
Display posts from previous:   
   Index -> Programming, Turing -> Turing Help
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 9 Posts ]
Jump to:   


Style:  
Search: