fork download
copy 
  1.  
  2. import java.util.*;
  3.  
  4. class SmallestPrimeFactor {
  5.     static final int MAXN = 1000000;
  6.     static int[] spf = new int[MAXN + 1]; // spf[i] -> smallest prime factor of i
  7.     static void computeSPF() {
  8.         // Initialize: har number ka spf khud se hi
  9.         for (int i = 2; i <= MAXN; i++) {
  10.             spf[i] = i;
  11.         }
  12.  
  13.         // Sieve logic
  14.         for (int i = 2;   i <= Math.sqrt(MAXN); i++) {
  15.             if (spf[i] == i) { // i prime hai
  16.                 for (int j = i * i; j <= MAXN; j += i) {
  17.                     if (spf[j] == j) {
  18.                         spf[j] = i; // sabse chhota prime factor assign karo
  19.                     }
  20.                 }
  21.             }
  22.         }
  23.     }
  24.  
  25.     // Function to get prime factorization of a number using spf[]
  26.     static List<Integer> getPrimeFactors(int n) {
  27.         List<Integer> factors = new ArrayList<>();
  28.         while (n != 1) {
  29.             factors.add(spf[n]);
  30.             n = n / spf[n];
  31.         }
  32.         return factors;
  33.     }
  34.  
  35.     public static void main(String[] args) {
  36.         // Precompute SPF for all numbers
  37.         computeSPF();
  38.  
  39.  
  40.         System.out.println("Smallest Prime Factors (2–20):");
  41.         for (int i = 2; i <= 20; i++) {
  42.             System.out.println(i + " -> " + spf[i]);
  43.         }
  44.  
  45.     }
  46. }
  47.  
Success #stdin #stdout 0.16s 59760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Smallest Prime Factors (2–20):
2 -> 2
3 -> 3
4 -> 2
5 -> 5
6 -> 2
7 -> 7
8 -> 2
9 -> 3
10 -> 2
11 -> 11
12 -> 2
13 -> 13
14 -> 2
15 -> 3
16 -> 2
17 -> 17
18 -> 2
19 -> 19
20 -> 2
https://ideone.com/VqvoAE
language:
Java (HotSpot 12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!