Monday 3 January 2022

Eratosthenes Sieve - Prime numbers in Java - Algorithm Example

Eratosthenes Sieve algorithm for checking prime numbers.

Maybe we should first ask, what is prime number?

If one number can be calculated by multiplying any two different numbers then this number is not a prime number (We do not take number 1 into consideration). As example we can take few numbers 3,4,5,9,11.
Number 3 is prime as you can't multiple any other two numbers and get it.
Number 4 is not a prime number as you can get it by multiplying number 2 with 2 and get result as 4.
Number 5 is prime as well, while number 9 is not a prime, as you can get is as result 3*3.
Number 11 is prime as you can't get it as result of multiplying any other two numbers.

You can say, yes, it is easy, and sure it is for smaller numbers, but when you get into 3 digits or even 4 it is bit harder to calculate. 

So how Eratosthenes sieve works.

Lets use number 117 for checking if it is prime number or not. Algorithm starts with simple numbers and multiply them until you get to number you want.
Starts with number 2 and start to calculate, 2*2, 2*3, 2*4, 2*5, 2*6, all results of this multiply will be marked as NOT PRIME in sieve as they are result of multiplying two numbers. We do multply and increasing numbers as long result is less then 117. Then we increase first number, now it is 3, 3*3, 3*4, 3*5, result or multiply are marked as NOT PRIME in sieve... Increasing first number to number 4? Nope, it doesn't use number 4 as it is not prime, and sieve knows it, because we marked it as not prime when we calculated 2*2. Next number will be 5, so 5*2, 5*3, 5*4... and so on, until we reach first number as number 117. At this point, all numbers in seive are marked as NOT PRIME, we should now just checked the sieve and see if our number is prime or not.

Have a look at code below. Algorithm will use same approach and print out if number is prime or not, with limit that user enters.

import java.io.*;

public class EratosthensSievePrimeNumbers {

    // Start of the program
    public static void main(String args[]) throws IOException {

        
        boolean[] sieve; // array to keep track if number is prime or not
                                    //value for each number will be true or false
        int index; // index used in for loops
        int jIndex; // jIndex second index used in for loops
        int limit; // limit for sieve, provided by user
        
        // used to read input from user
        BufferedReader readUserInput = new BufferedReader(new InputStreamReader(System.in));

        System.out.print("Enter limit for prime number search: ");
        limit = Integer.parseInt(readUserInput.readLine());
        sieve = new boolean[limit]; // first: allocate memory

        for (index = 2; index < limit; index++) {
            sieve[index] = true; // setting all numbers as potential prime numbers
        }
        for (index = 2; index < limit; index++){
            if (sieve[index]) {
                for (jIndex = index + index; jIndex < limit; jIndex += index)
                    // exclude all numbers that we are multiplying by index from the list
                    sieve[jIndex] = false;
            } // 2 * i, 3 * i ...
        }
        // Going over list and printing out all prime numbers that still have true as value.
        for (index = 2; index < limit; index++){
            if (sieve[index]){
                System.out.println("Prime number is: " + index);
            }
        }
    }
}

I hope this will be helpful for anyone interested to see how Eratosthenes Sieve works, if you still have any doubts, add a comment with your question and I will try to answer it.

Sunday 5 February 2017

Can we create Matrix using AI?

Would it be possible for us to create real time world simulation?

We started using super computers with few thousands of processors, unbelievable number of RAM, insane Internet speed, and all that working as one unit.

We use them for predicting climate, solving problems, do different types of simulations, but can they run Matrix?
On first look you could think, ok, how hard it can be?

Let's try to think for few minutes what we need for building Matrix.
For this purpose we will speak in OOP world, so describing what kind of "objects" we need.

First we need "World", he will be filled with "People", "Animals", "Physics rules", "Oceans", "Nature", "Rivers", "Mountains", "Threes", "Cars", "Homes", ... and many other things.
Now you can think, ok, at some point I will create all of them, then you can think what to do next...?

What is the main ingredient for life itself? It's Sun. So we need to map our whole planetary system.
On then add "Sun", "Moon", "Mars" and others...
Create them and just add basic rules, all planets are circling around soon at some speeds, they are spinning at certain speeds, and we did that, perfect.

Now we have light on our planet, hmm, so now what we need is "Climate", some times we have sunny days, some days rain, some days wind, snow,...

Let's assume we did that too, now we have day and night zones, climate, so we can work on photosynthesis because we need oxygen. We did that too, ok, at this point it started to be very complex and we just started.

Let's say everything is done, let us concentrate only at one place, one city, and then on block.
How many people live there? How many streets, shops, jobs, cars, dogs, cats are there?
And you fill all that info, what is left is our SOUL!

We still can't create that good AI to simulate our way of thinking. Our way of getting knowledge, our way of getting friends, every person has something unique and that computer can't simulate. Still...

Best companies in the world didn't even scratch the surface what is our brain capable of.

When we count all necessary things we need to create in Matrix, your brain already started imagine that in your head, all the places, streets, different people, worlds and that machine can't do...

Machines are now just capable to use our data we provide them and manipulate in some sort to get a result we think it is good.
I hope it will stay like that for a long time, because if somebody do create that good program, we will all be without job :)

Let's say in we do create that good AI, what do we need more? Can you imagine how big data centers it will require, just to store memories of 1,000 people? Matrix is still out our reach, and it will take us some time to reach that goal, maybe we will never reach it but who knows, maybe where are we now is only one big simulation...

If you did like our story, and your are looking of more, please subscribe to our blog, post some comments, like us on Facebook, share it and enjoy.

Kind regards,
M.L.