Math

Factor of a number N is a number d such that d divides N.
That is, N % d == 0.

Example:

For number 6, the factors are 1, 2, 3 and 6.

This is best explained through working our way through some sample problems.

Walkthrough examples :

FACTORS VERIFYPRIME SIEVE

This is another very important concept in computer science. Particularly because of how data is represented within machines.
Taking up bit arithmetic as a topic separately, let us initiate with understanding what those terms even mean.

In our customary base-ten system, we have digits for the numbers zero through nine. We do not have a single-digit numeral for “ten”. Yes, we write “10”, but its two digits; we have no single solitary digit that stands for “ten”.

There are 10 digits using which we represent all the numbers. Hence the base 10 system.

Similarily, binary number system or base 2 number system has only 2 digits 0, 1. Hex number system or base 16 number system has 16 digits ( 0, 1, 2 .. 9, A, B, .. F ). In general a N base number system has N digits, 0, 1, ... N-1 ( The digits usually after 9 are represented as A, B and so on ).

Base systems like binary and hexadecimal seem a bit strange at first. The key is understanding how different systems “tick over” like an odometer when they are full.

Base 10, our decimal system, “ticks over” when it gets 10 items, creating a new digit. We wait 60 seconds before “ticking over” to a new minute. Hexadecimal and binary are similar, but tick over every 16 and 2 items, respectively.

In computers, numbers are internally represented in binary number system.
We explore more in next slides.

Way back in the day, we didn’t have base systems! It was uphill both ways, through the snow and blazing heat. When you wanted to count one, you’d write:

|

When you wanted 5, you’d write

|||||

And clearly, 1 + 5 = 6

| + ||||| = ||||||

This is the simplest way of counting.

The value of any number = number of |’s

Unary, where we just write 1, 11, 111… just goes on forever. Binary, with two options (1 and 0) looks like this:

    1: 1
    2: 10 (we’re full – tick over)
    3: 11
    4: 100 (we’re full again – tick over)
    5: 101
    6: 110
    7: 111
    8: 1000 (tick over again)

and so on …

Now, how do we convert an arbitrary binary number to its decimal equivalent? Obviously counting and matching is not an option.

Let us first look at the value of 10000...n times ( 1 followed by n 0s ):

This number will only come after we have tried all possible n digit numbers in the binary system which has:

      2 * 2 * 2 * .. n times possibilities  ( every position can either have 0 or 1 ) 
   =  2^n possibility which covers numbers from 0 to 2^n - 1.

So, the value of 1000..n times = 2ⁿ.

Now any number like 1010110 can be expressed as 1000000 + 10000 + 100 + 10 = 2^6 + 2^4 + 2^2 + 2^1.

Hence, if the binary representation is An An-1 An-2 ... A1 A0, then the corresponding value is

A0 * 2^0 + A1 * 2^1 + A2 * 2^2 + .... + An * 2^n

Now look at the reverse process. Which is given a decimal number N, how do we convert it to binary.
To do this conversion, we need to divide repeatedly by 2, keeping track of the remainders as we go. Watch below:
Let us say our number is 357.

Thus the number converts to 101100101

Walkthrough Example :
DECBIN

A base N number system has N digits. The process of conversion of N based number to decimal and vice versa is very similar to the binary number system process we just saw.
The only thing that changes is that 2 is replaced by N.
So, if the N based number system representation is An An-1 ... A2 A1 A0, then the corresponding decimal value is

    A0 * N^0 + A1 * N^1 + A2 * N^2 + ... 

The reverse process is also exactly similar. We keep dividing by N, keeping track of the remainders as we go.

Let us say our number is 357, and N = 7.

                1       R0
             ---------
           7 |  7       R2
             ---------
           7 |  51      R0
             ---------
           7 |  357  

Thus the number converts to 1020 in base 7.