Prime Numbers

List of Prime Numbers

The below program finds n-number of prime numbers.

Step 1: Add 2,3 to the list, I've used malloc to add two space to the pointer *prime_list. The idea is to have a dynamic array list with only its address being passed to the prime adding function

Step 2: Prime adding function *Add_NewPrime returns the address of the updated prime list to our *prime_list pointer until the desired list of prime numbers is filled.

Step 3: The main prime finding is happening in the *Add_NewPrime function. We pass the address of the prime count (which is 2 initially), the new prime might be the last prime number in the list + 2. For example when *Add_NewPrime is first called our list has 2&3 and the New_Prime = 5 (3+2)

Step 4: Now we have to check whether the New_prime is divisible by the Primes which is already in the list, then we have to increment 2 to the New_prime. For example, assume we already added 2,3,5,7 and now the New_prime is 9(7+2), when j=1, 3 divides 9, so now 9 is incremented to 11 and j becomes 1, we don't have to check 2 since all our new primes are odd number.

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

int *Add_NewPrime(int *prime_list,int *prime_count);
bool IsDivisible(int *dividend, int *divisor);

int main()
{
    int Pnum_count = 10001;
    int i;
    int *prime_list=malloc(2*sizeof(int)); //Initially we allocate 2 space to prime_numbers list
    *(prime_list+0) = 2;
    *(prime_list+1) = 3;
    int pcount=2;

    for(i=0;i<Pnum_count;i++)
    {
        prime_list = Add_NewPrime(prime_list,&pcount);
        printf("%d\n",*(prime_list+i));
    }
    return 0;


}

int *Add_NewPrime(int *prime_list,int *prime_count)
{
    int New_prime = *(prime_list+(*(prime_count)-1))+2;
    int j;

    for(j=1;j<*(prime_count);j++)
    {
        if(IsDivisible(&New_prime,(prime_list+j))==true) //Check the "New Potential Prime" is divisible by the primes already in the list
        {
            New_prime = New_prime + 2;//So the potential New_prime is not passed the test so we increment the New_prime + 2
            j=1;
        }
    }

    // Allot new space to the prime_list
    int *temp;
    temp=realloc(prime_list , (*(prime_count)+1)*1*sizeof(int)); // give the pointer some (+1 int) memory each time
    if (temp != NULL )
    {
        prime_list=temp; //Memory added here
    }
    else
    {
        printf("Error Allocating Memory");
    }

    // Add the new prime number to the list
    *(prime_list+*(prime_count))=New_prime;
    *(prime_count)=*(prime_count)+1;
    return prime_list;
}

bool IsDivisible(int *dividend, int *divisor)
{
    int remainder =(*dividend)- (int)((*(dividend)/(*(divisor)))*(*divisor));
    if(remainder == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

PRIME FACTORIZATION

The below program finds the prime factors of any integer n, it utilizes *Add_NewPrime function from the above program and uses new function *Add_PrimeFactor to keep the list of prime factors found for our input integer.

Step 1: The idea is to divide the number until it becomes 1. First we start with 2 prime numbers 2,3 in our list.

Step 2: We check whether our input is divisible by the prime numbers in the list (2,3). If yes then whichever prime divides is added to the *prime_factors list.

Step 3: If no then new prime is added to the prime list (ie,5) and once again we try reducing our input number with the new prime (5).

For example: Lets take an input number 55860

First we have 2,3 in the prime list

2 divides 55860 and reduces the number to 27930 and once again divides the number to 13965 (2,2 is in the *prime_factors list)

2 couldn't reduce the number 13965 but 3 divides it to 4655 (2,2,3 is in the *prime_factors list)

Once again we try with 2,3 but neither divides the number 4655, so we add a new prime 5 to the *prime_numbers (2,3,5 is in the *prime_numbers list) we check with our newly added prime 5 and it divides it to 931.

Now again we try with 2,3,5 which is not dividing 931 so we add 7 to the list and check with 7 and it divides 931 to 133 (2,3,5,7 is in *prime_numbers list and 2,2,3,5,7 is in *prime_factors list)

Now is 133 divisible by 2 or 3 or 5 or 7 it is divisible by 7 and it the value becomes 19. Now we by adding new prime numbers to the list but only 19 will work and the loop ends as our input becomes 1.

Finally, 2,3,5,7,11,13,17,19 are in *prime_numbers list and 2,2,3,5,7,7,19 are in the *prime_factors list which is the output.

To handle very big numbers slight modification has to be done such as the input has to be double variable instead of int and the function bool IsDivisible should be modified to handle double variable as well.

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

int *Add_NewPrime(int *prime_numbers,int *prime_count);
int *Add_PrimeFactor(int *prime_factor,int *the_prime,int *prime_factor_counter);
bool IsDivisible(int *dividend, int *divisor);

int main()
{
    // Prime Factorization Problem
    int input_number = 6008513; //Input from user
    int prime_counter = 0; //To keep track of the number of prime numbers added
    int primefactors_counter =0;//To keep track of the number of prime factors added
    int *prime_numbers;//Address to store the prime list
    int *prime_factors;//Address to store the prime factors

    // First add prime number 2,3 bcoz rest all primes are odd can be derived from 3
    prime_numbers=malloc(2*sizeof(int)); //Initially we allocate 2 space to prime_numbers list
    prime_factors=malloc(1*sizeof(int)); //Initially we allocate 1 space to prime_factors list to avoid error during realloc
    *(prime_numbers+0) = 2;
    *(prime_numbers+1) = 3;
    prime_counter = prime_counter + 2;
    int chk_val;

    // Loop until the input_number is divisible
    int i = 0;
    do
    {
        for(;i<prime_counter;i++)//Note: there is no i=0 initialization, bcoz for loop should restart from where we left
        {
            if(IsDivisible(&input_number,(prime_numbers+i))==true)
            {
                input_number = input_number / (*(prime_numbers+i)); //Divide the input number by the found prime
                prime_factors = Add_PrimeFactor(prime_factors,(prime_numbers+i),&primefactors_counter); //Add the found prime to our list for output
                primefactors_counter++; //Increment the prime_factors_counter
                i=0; //i becomes zero only after the input_number is updated and new_number is formed
                break; // break away from the for loop and starts reducing the new_number
            }
        }
        if(input_number ==1)//So the primes in our list successfully reduced the input_number to 1
        {
            break;//Loop exits when the input_number is reduced to 1
        }
        else// Since the primes in our list couldn't reduce the input_number to 1 we update
        {
            if(i!=0)// If i =0 then infact the primes in our list is a factor so no need to add new prime numbers to list
            {
                prime_numbers = Add_NewPrime(prime_numbers,&prime_counter);//Prime number list updated with one more member
                prime_counter++; //prime_counter is updated, now once again the for loop will restart with verifying the added_prime
                chk_val = *(prime_numbers+prime_counter-1);
            }
        }
    }while(1==1);// Infinite loop

    int product =1; // Just to print out the input_value
    for(i=0;i<primefactors_counter;i++)
    {
        printf("%d\n",*(prime_factors+i));
        product = product * (*(prime_factors+i));
    }

    printf("\n\n The input is %d",product);
    return 0;
}

int *Add_NewPrime(int *prime_list,int *prime_count)
{
    int New_prime = *(prime_list+(*(prime_count)-1))+2;
    int j;

    for(j=0;j<*(prime_count);j++)
    {
        if(IsDivisible(&New_prime,(prime_list+j))==true) //Check the "New Potential Prime" is divisible by the primes already in the list
        {
            New_prime = New_prime + 2;//So the potential New_prime is not passed the test so we increment the New_prime + 2
            j=0;
        }
    }

    // Allot new space to the prime_list
    int *temp;
    temp=realloc(prime_list , (*(prime_count)+1)*1*sizeof(int)); // give the pointer some (+1 int) memory each time
    if (temp != NULL )
    {
        prime_list=temp; //Memory added here
    }
    else
    {
        printf("Error Allocating Memory");
    }

    // Add the new prime number to the list
    *(prime_list+*(prime_count))=New_prime;
    return prime_list;
}

int *Add_PrimeFactor(int *prime_factors,int *the_prime,int *prime_factor_counter)
{
    // Allot new space to the prime_factors_list
    int *temp=realloc(prime_factors,(*(prime_factor_counter)+1)*1*sizeof(int)); // give the pointer some (+1 int) memory each time
    if (temp != NULL )
    {
        prime_factors=temp; //Memory added here
    }
    else
    {
        printf("Error Allocating Memory");
    }

    // Add the new prime number to the list
    *(prime_factors+*(prime_factor_counter))=*(the_prime);
     return prime_factors;
}

bool IsDivisible(int *dividend, int *divisor)
{
    int remainder =(*dividend)- (int)((*(dividend)/(*(divisor)))*(*divisor));
    if(remainder == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}