Make delicious recipes!

Finding first N prime numbers



Problem: Given some integer N, find first N prime numbers.


Solution: Prime number is one which is divisible only by itself or by 1.
First few prime numbers are 2, 3, 5, 7, 11, 13, 17 and so on.



import java.util.ArrayList;
import java.util.List;

public class PrimeNumbers 
{

    // basic function to check if a given integer is prime or not
    static boolean checkPrime(int i) 
    {
        int j=2;
        while (j<i)
        {
            if (i%j==0)
                return false;
            j++;
            
            // if j has been incremented till square-root(i), then look no further
            if (i/j < j)
                break;
        }
        return true;
    }


    // optimization over the above function
    // An integer is checked for primeness given all the primes below that number.
    // It is more efficient, because it does not check division by prime-multiples (example:4) if
    // we have already checked division by primes (example: 2)
    static boolean checkPrime(int i, List<Integer> primes) 
    {
        for (int j : primes)
            if (i%j==0)
                return false;
        return true;
    }


    // Driver function to test the above functions
    public static void main(String[] args) 
    {
        List <Integer> primes = new ArrayList<Integer> ();
        primes.add(2);

        int i=3;
        while (primes.size() < 100)
        {
            // determine prime division by efficient function
            if (checkPrime(i, primes))
            {
                primes.add(i);
                // test if the first implementation of prime function also returns the same
                System.out.println (i + " = " + checkPrime(i) + ", " + (i+2) + " = " + checkPrime(i+2));
            }
            i=i+2;
        }
    }
}




Sample output:
3 = true, 5 = true
5 = true, 7 = true
7 = true, 9 = false
11 = true, 13 = true
13 = true, 15 = false
17 = true, 19 = true
19 = true, 21 = false
23 = true, 25 = false
29 = true, 31 = true
31 = true, 33 = false
37 = true, 39 = false
41 = true, 43 = true
43 = true, 45 = false
47 = true, 49 = false
53 = true, 55 = false
59 = true, 61 = true
61 = true, 63 = false
67 = true, 69 = false
71 = true, 73 = true
73 = true, 75 = false
79 = true, 81 = false
83 = true, 85 = false
89 = true, 91 = false
97 = true, 99 = false
101 = true, 103 = true
103 = true, 105 = false
107 = true, 109 = true
109 = true, 111 = false
113 = true, 115 = false
127 = true, 129 = false
131 = true, 133 = false
137 = true, 139 = true
139 = true, 141 = false
149 = true, 151 = true
151 = true, 153 = false
157 = true, 159 = false
163 = true, 165 = false
167 = true, 169 = false
173 = true, 175 = false
179 = true, 181 = true
181 = true, 183 = false
191 = true, 193 = true
193 = true, 195 = false
197 = true, 199 = true
199 = true, 201 = false
211 = true, 213 = false
223 = true, 225 = false
227 = true, 229 = true
229 = true, 231 = false
233 = true, 235 = false
239 = true, 241 = true
241 = true, 243 = false
251 = true, 253 = false
257 = true, 259 = false
263 = true, 265 = false
269 = true, 271 = true
271 = true, 273 = false
277 = true, 279 = false
281 = true, 283 = true
283 = true, 285 = false
293 = true, 295 = false
307 = true, 309 = false
311 = true, 313 = true
313 = true, 315 = false
317 = true, 319 = false
331 = true, 333 = false
337 = true, 339 = false
347 = true, 349 = true
349 = true, 351 = false
353 = true, 355 = false
359 = true, 361 = false
367 = true, 369 = false
373 = true, 375 = false
379 = true, 381 = false
383 = true, 385 = false
389 = true, 391 = false
397 = true, 399 = false
401 = true, 403 = false
409 = true, 411 = false
419 = true, 421 = true
421 = true, 423 = false
431 = true, 433 = true
433 = true, 435 = false
439 = true, 441 = false
443 = true, 445 = false
449 = true, 451 = false
457 = true, 459 = false
461 = true, 463 = true
463 = true, 465 = false
467 = true, 469 = false
479 = true, 481 = false
487 = true, 489 = false
491 = true, 493 = false
499 = true, 501 = false
503 = true, 505 = false
509 = true, 511 = false
521 = true, 523 = true
523 = true, 525 = false
541 = true, 543 = false




Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal