Program opened below. You can scroll through the algorithm, Java code and output.
Program 79
Lucky Numbers up to N
Question
Generate lucky numbers from the natural numbers 1..N by repeatedly removing every second, third, fourth and subsequent number according to the current sequence position.
Algorithm
Step 1: Start.
Step 2: Declare the variables and data structures required for the task.
Step 3: Input limit N and validate it.
Step 4: Create a list containing integers 1 through N.
Step 5: Initialize the counters, flags, accumulators or result structures needed by the solution.
Step 6: Set index=1, representing removal of every second item first.
Step 7: While index is less than list size, remove items at positions index, index+(index+1), and so on.
Step 8: Increase index by one for the next elimination pass.
Step 9: Store the computed result and prepare it for display.
Step 10: Display the remaining lucky numbers.
Step 11: Stop.
Java program
Javaimport java.util.*;
class LuckyNumbers {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if (n < 1 || n > 10000) {
System.out.println("INVALID INPUT");
return;
}
ArrayList<Integer> list = new ArrayList<>();
for (int i = 1; i <= n; i++) {
list.add(i);
}
int index = 1;
while (index < list.size()) {
int step = list.get(index);
for (int i = step - 1; i < list.size(); i += step - 1) {
list.set(i, 0);
}
list.removeIf(v -> v == 0);
index++;
}
System.out.println(list);
}
}Sample output
Input: 20
Output:
[1, 3, 7, 13, 19]