# Assignment1: Prime Number

## Definition of prime number
A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. (https://en.wikipedia.org/wiki/Prime_number)

## C code

#include <stdio.h> 
 
int IsPrimeNumber(int n); 
int main(void)
{
    int i = 0;
    for (i = 1; i <= 20; i++) 
    {
        if (IsPrimeNumber(i)) 
        {
            printf("%3d ", i); 
        }
    }
    printf("\n");
    return 0;
}
 
 
int IsPrimeNumber(int n)
{
    int i = 0;
    int last = n / 2;  
    if (n <= 1)
    {
        return 0;
    }
                       
    for (i = 2; i <= last; i++) 
    {
        if ((n%i) == 0)
        {
            return 0; 
        }
    }
    return 1; 
}

## Assembly code

.data
argument: .word 20 # Number to find the prime number
str1: .string " is prime number"

.text
main:
			# set number
			lw     a2, argument 
			li     a3, 0	
			jal    ra, Loop1
			
			# Exit program
			li     a0, 10
			ecall
            
Loop1:
			addi   a3, a3, 1
			blt    a3, a2, IsPrime  
			ret

IsPrime:
			li     t3, 2
			li     t4, 1 
			div    t5, a3, t3 	
			blt    a3, t3, Loop1	
			addi   t5, t5, 1
			j      Loop2
		
Loop2:			
			addi   t4, t4, 1		
			bge    t4, t5, PrintResult 
			rem    t6, a3, t4
			beq    t6, zero, Loop1 # return
			j      Loop2

PrintResult:
			mv     t0, a3
			mv     a1, t0
			li     a0, 1
			ecall
			
			la     a1, str1
			li     a0, 4 	
			ecall

			j      Loop1

## Explaination
### Fucntions
#### main
Main function is to excute the program
#### Loop1
Loop1 function is to repeat codes(literally loop function). Before the function, target number for finding prime numbers should set. E.g.) If target number is 10, then the Loop1 function will repeat 10 times.
#### IsPrime
IsPrime function is to ascertain whether a number is prime or not.
#### Loop2
Loop2 function is a loop function in IsPrime function. It checks numbers and when it finds prime number print results.
#### PrintResult
This function is to show results of prime numbers.

### Pipeline
1) IF: Instruction Fetch
2) ID: Instruction Decode / Register file read
3) EX: Execute / Address calculation
4) MEM: Memory Address
5) WB: Write Back

At the first line in the main function.
`lw x12 0(x12)`
Firstly, in IF stage, the CPU fetches instruction.

Here ID stage, data is loaded into `x12` as you see Read data `0xc` and Read data `0x0` in the Registers.

And then it excuted in EX stage.

In this instuction, data is `argument: .word 20"`. Therefore you can see this word data is saved into `x12`.

However instuction `lw x12 0(x12)` is only for loading data, so there is no conditional statement or calculation. I will show you what happens in the system during other instruction.

For example, here is `addi x13 x0 0`, which is next instruction.
This is to save value that sum of `x0` and `0` into `x13`, so `x13` will be `0`.

And if there is jump instruction, you can save current address into `ra(x1)`. After finishing function you can return to the previous address. And IF stage will be started in other position that you jumped.

In ID stage with blt instruction `blt x13 x12 8`, two values(`x13 and x12`) are compared and branched depending on the result.
blt: branch if less than ~
bge: branch if grater than or equal ~
beq: branch if equal ~
bne: branch if not equal ~

## Result
I set 20 as a target number. It means the system will find prime numbers from 2 to 20.
And results are 2, 3, 5, 7, 11, 13, 17 and 19.

## Writer
Soonmyun Jang
P76077133
[e-mail]