# Seventh Week Examples:   Testing for Prime Numbers.   Factoring

Following D. Milicic Eighth Week Examples.

## Checking primality

The first program is inefficient.
```/**********************************************************************
A. Treibergs                                                      2-9-6

Silly prime checking

prime1.c
**********************************************************************/

# include <stdio.h>
# include <stdlib.h>

int
main(void)
{

int n, p;

printf("Prime Checking\n\n Input an integer bigger than 1 : ");
scanf("%d",&n);

p = 2;

while(p < n)
{
if (n % p == 0)
{
break;
}
else
p = p+1;
}
if (p == n)
printf(" %d is prime!\n",n);
else
printf(" %d is not prime!\n",n);

return EXIT_SUCCESS;

}
```

## Checking primality 2

A better program. The loop continues to the square root of the number only, this time.
```/**********************************************************************
A. Treibergs                                                      2-9-6

Better prime checking

prime2.c
**********************************************************************/

# include <stdio.h>
# include <stdlib.h>

int
main ( void )
{
int n, p, flag;

printf ( "Input an integer bigger than 1 : ");
scanf ( "%d", &n );

flag = 0;
p = 2;

while ( p*p <= n )
{
if (n % p == 0)
{
flag = 1;
break;
}
else
p = p+1;
}

if (flag == 0)
printf("%d is prime!\n",n);
else
printf("%d is not prime!\n",n);

return EXIT_SUCCESS;
}
```

## Factorization

```/**********************************************************************
A. Treibergs                                                      2-9-6

factoring a number

factor.c
**********************************************************************/

# include <stdio.h>
# include <stdlib.h>

int
factor ( int n )
{
int p;
p=2;

while ( p*p <= n )
{
if ( n % p == 0)
return(p);

p=p+1;
}

return(n);
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

int
main(void)
{
int n, fact;

printf ( "Input a number : " );
scanf ( "%d", &n );

printf("Prime factors of %d are: ",n);

do
{
fact = factor(n);
printf("%d  ",fact);
n = n/fact;
}
while(n != 1);

printf("\n");

return EXIT_SUCCESS;
}

```