Primes generator 61

Hello! I have solved this problem for myself and I looked for the generated primes and they seem to be ok. But my problem is in the note under the task saying

"Take care of implementing the algorithm efficiently - with proper approach all 200000 primes should be generated in about a second (somewhat slower with scripting languages like Python, or older computer)."

I tried to optimize the code but I did not succeed. I used the trial division method, I also tried to make time limited program (program execution ends in 1 sec and then print the number of primes generated) and my code can generate in one second first (cca.) 15.000 primes. To solve the task with provided input on my pc takes somewhat less than a minute. (looks like the square root is quite time consuming operation).

So my question is: If I post answer with output generated by my computer and not the server, would it be considered as a cheating? (I am still not 100% sure if my solution is correct because I did not post my answer) Should I think of different approach? (I could not think of any better solution for now)

Thanks for reading my problem.

(I just realized that I posted this to wrong branch I am sorry for that)

(Correct should be Hello Radovan! But it doesn't matter :D)

There is a screenshot of program output: https://imgur.com/uvHvqXW

My code:

import java.util.HashMap;//used libraries import java.util.Map; import java.util.Scanner;

public class PrimeGenerator {

static String input = "9\n"
        + "111714 186939 150238 137073 113604 129254 158384 125959 104970";//input provided by CodeAbbey

static Map<Integer, Long> primes = new HashMap<Integer, Long>();//Map of primes (each prime has its own index)
static Scanner in = new Scanner(input);//object used for reading input
static int cycle = in.nextInt();//read first number i.e how many indexes

public static void main(String[] args)//program runs here
{
    long number = 2;//statically defining first two primes since their square root is less than 2
    primes.put(1, number);// index 1 prime 2
    number = 3;
    primes.put(2, number);// index 2 prime 3

    generatePrimes();


    for (int i = 0; i < cycle; i++)//prints answer
    {
        System.out.print(primes.get(in.nextInt())+" ");
    }
}

public static int maxIndex()//program checks the max index which is needed and that is
{//upper limit of generating primes i.e the programs stops when prime with max index is generated
    Scanner inp = new Scanner(input);
    int max = -1;
    for (int j = 0; inp.hasNext(); j++)
    {
        int i = inp.nextInt();
        if (max < i) max = i;
    }
    return max;
}

public static void generatePrimes()
{
    int index = 3;//first generated prime will have index 3 since we already statically defined first two primes
    int maxIndex = maxIndex();

    for (long number = 5; index != maxIndex; number += 2)//generate primes until max index is not reached then stop
    {//primes are only odd numbers (except 2 of course) so at the end of loop add 2 instead of 1
        int square = (int) (Math.sqrt(number));//square root of current number (as integer without the decimal part)
        boolean prime = true;

        for (int root = square; root > 1; root--)//check if square root is divisible (with no remaining) by any smaller number
        {//and if yes, then it's not a prime
            double c = number / (double) root;

            if (c % 1 == 0) //check if number has remaining, if number is divisible by square or any number less than square, it is component
            {
                prime = false;
                break;
            }
        }

        if (prime)//if our number always had decimal part after dividing until it reached 1
        {//then it is a prime, raise index and write it to map
            index++;
            primes.put(index, number);
        }
    }
}

}

I hope it is readable.

Oh, and thanks for respond ^_^ !

Hello Rodion!

So I already solved that problem! I edited that loop (while I was ediing it I also noticed that I have a mistake in code) I cut time down to 7 seconds. It's not really 1 second like in note under the task and unfortunately the server could not process it so I had to run it on my machine. Here is the screenshot While I was checking the correctness of generated primes (that is why I said that I had a mistake in code)

I noticed that there were already some explanations and methods and even the code! (I didn't read it before finishing task) and their trial divison method was limited by the biggest number. when I tried their method (which used really big array) it took like 7 seconds to compile so maybe their was even more effective but I posted my solution of course.

I just hope it's okay that my solution took 7 seconds to compile on my notebook and I didn't post solution compiled via server. I can post a link of that page with explanation if you are curoious.

Don't write that many comments

This was my first post of my code somewhere so I wanted it to be as much readable as possible. But I also have a troubles with reading code of someone else and I think that leaving comments is nice habit. (But yes, I added just too much comments here)

You may be curious to read "Clean Code" by Robert Martin (the first 1/3 of the book, no more) for more ideas :) Thanks for tip! I will at least write it down so I can check it out later.

And thanks for help!