A variable holds one value. An array holds a whole row of values under one name. This page starts with notes on arrays and the two examples from class. Then you use arrays to find every prime number up to 10,000 and to break a number into its prime factors.
Array notes · Two class examples · Two lab problems
Notes
Arrays in Java
What is an array?
An array is a row of numbered boxes. Three rules describe it.
Every box holds the same type of value. An int[] holds only int values.
The number of boxes is chosen when the array is made, and it never changes.
Each box has a number called its index. The first index is 0.
Making an array
There are two ways. Use the first when you know how many boxes you need but not the values yet.
// Five boxes for integers. Every box starts at 0.
int[] arr = new int[5];
Read int[] as “array of ints.” The same pattern works for other types.
What the boxes hold before you put anything in them
Array made with new
Starting value in every box
new int[5]
0
new double[5]
0.0
new boolean[5]
false
Using one box
Write the array’s name and then the index in square brackets. That names one box, and you can use it like any other variable.
int[] arr = new int[5];
arr[0] = 10; // put 10 in the first box
arr[1] = 20;
arr[2] = 30;
arr[3] = 40;
arr[4] = 50; // the last box
System.out.println(arr[2]); // prints 30
arr[2] = arr[2] + 1; // the box now holds 31
arr after the first five assignments
Index
0
1
2
3
4
Value
10
20
30
40
50
Counting starts at zero. An array with five boxes has indexes 0 through 4. The last index is always one less than the number of boxes.
How many boxes?
Every array knows its own size. Write the array’s name, a dot, and length.
System.out.println(arr.length); // prints 5
There are no parentheses after length for an array. A String uses word.length() with parentheses. An array uses arr.length without them.
Visiting every box with a loop
Arrays and for loops work together. Let the loop variable be the index. Start it at 0 and keep going while it is less than arr.length.
for (int i = 0; i < arr.length; i++)
{
System.out.println("Element at index " + i + " : " + arr[i]);
}
The same loop can fill an array. This one puts a random number from 0 through 1000 in each of 1,000 boxes. It needs import java.util.Random; at the top of the file.
int[] bigArr = new int[1000];
Random rand = new Random();
for (int i = 0; i < bigArr.length; i++)
{
bigArr[i] = rand.nextInt(1001);
}
Out of bounds
If you ask for a box that does not exist, the program stops with an error.
int[] arr = new int[5];
arr[5] = 60; // there is no box 5
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException:
Index 5 out of bounds for length 5
The message tells you the index you used and the length of the array. When you see it, check where your loop starts and stops. A loop that uses i <= arr.length goes one box too far. Use i < arr.length.
Arrays of other types
An array can hold any one type: double[], boolean[], char[], String[]. This example turns a word into an array of characters, fills the array in reverse order, and turns it back into a word.
String word = "hotdog";
char[] letters = word.toCharArray();
for (int i = 0; i < word.length(); i++)
{
letters[i] = word.charAt(word.length() - (i + 1));
}
word = String.valueOf(letters);
System.out.println(word); // prints godtoh
Quick reference
To do this
Write this
Make an array of 5 ints
int[] arr = new int[5];
Make an array from known values
int[] arr = {4, 8, 15};
Put a value in a box
arr[0] = 10;
Read a value from a box
int x = arr[0];
Find the number of boxes
arr.length
Name the last box
arr[arr.length - 1]
Visit every box
for (int i = 0; i < arr.length; i++)
In class
Class examples
We work these two together before the lab. Keep them nearby. Both lab problems use the same moves.
Visit every box · Change each value
1. Baby’s First Array
Take an array of integers and add 1 to every value. The array {1, 2, 3, 4, -3} becomes {2, 3, 4, 5, -2}.
int[] numbers = {1, 2, 3, 4, -3};
for (int i = 0; i < numbers.length; i++)
{
numbers[i] = numbers[i] + 1;
}
What to notice. The loop variable i is the index. Each time through, numbers[i] names a different box.
Fill an array · Use earlier boxes
2. Jury-Rigged Fibonacci Sequence
Start with an array whose first two boxes hold numbers. Fill each remaining box with the sum of the two boxes before it. Starting from 5 and 3, an array of ten boxes ends as {5, 3, 8, 11, 19, 30, 49, 79, 128, 207}.
int[] sequence = new int[10];
sequence[0] = 5;
sequence[1] = 3;
for (int i = 2; i < sequence.length; i++)
{
sequence[i] = sequence[i - 1] + sequence[i - 2];
}
What to notice. The loop starts at 2 because boxes 0 and 1 are already filled. The index can be a calculation, such as i - 1.
Starter code
Save this in src as ArrayLab.java. Fill in your name and date and run it once. You should see the two problem labels. Write each solution in main below its label.
/*
* Name:
* Project: Array Lab
* Date:
*/
import java.util.Scanner;
public class ArrayLab
{
public static void main(String[] args)
{
Scanner keyboard = new Scanner(System.in);
System.out.println("Problem 3: The Sieve of Eratosthenes");
// TODO: Write Problem 3 here.
System.out.println("Problem 4: Prime factorization");
// TODO: Write Problem 4 here.
keyboard.close();
}
}
Brace style. Put each opening brace on its own line, and line up each closing brace with its opening brace. Indent the lines inside a block by four spaces.
Lab problem 3
The Sieve of Eratosthenes
boolean array · Nested loops · Building a second array
Find every prime number from 2 through 10000 and store them, in order, in an array of integers named primes. Print how many primes you found. You need primes again in Problem 4.
Sift the twos, sift the threes— The Sieve of Eratosthenes! When the multiples sublime, The numbers that remain are prime!
The method
Strike out 0 and 1.
Let n = 2.
Strike out every multiple of n that is greater than n.
Add one to n.
Repeat steps 3 and 4 until n is greater than the last number in the array.
Stop. The numbers that remain are prime.
Try it on paper first
Write the numbers 2 through 30. Strike out the multiples of 2 greater than 2, then the multiples of 3 greater than 3, then the multiples of 5 greater than 5. Compare with this table.
After striking multiples of
Numbers that remain
2
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
3
2 3 5 7 11 13 17 19 23 25 29
5
2 3 5 7 11 13 17 19 23 29
Your program does the same thing with a much longer list.
How to build it
Step 1. Make the checklist.
Make an array of boolean values with one box for every number from 0 through 10000. The index is the number. The value answers one question: has this number been struck out?
boolean[] struckOut = new boolean[10001];
The size is 10001 so that index 10000 exists. Every box starts as false, so at the start nothing is struck out.
Step 2. Strike out 0 and 1.
Set those two boxes to true. This takes two lines and no loop.
Step 3. Strike out the multiples.
You need a loop inside a loop.
The outer loop chooses n. It starts at 2 and goes up by one.
The inner loop visits the multiples of n that are greater than n. It starts at 2 * n, goes up by n each time, and stops once it passes 10000. Each box it visits is set to true.
You have written this before. The inner loop is Assignment 2, Activity 6, and the two loops together are Activity 12. There you printed each multiple. Here you set struckOut[multiple] = true; instead.
Check. Before going on, print struckOut[9], struckOut[11], and struckOut[25]. You should see true, false, true.
Step 4. Count the primes.
Make a counter that starts at 0. Loop through the whole checklist. Each time a box is still false, add one to the counter. You need this count because an array’s size must be chosen when the array is made.
Step 5. Collect the primes.
Make the array of primes with exactly as many boxes as your count. Then loop through the checklist one more time and copy each number that is still false into primes.
This step uses two positions at once.
i walks through the checklist, one box at a time.
A second variable, such as next, remembers which box of primes is open. It starts at 0 and goes up by one only when you store a prime.
The first few times through the loop in Step 5
i
struckOut[i]
What happens
next afterward
0
true
Nothing
0
1
true
Nothing
0
2
false
primes[0] becomes 2
1
3
false
primes[1] becomes 3
2
4
true
Nothing
2
5
false
primes[2] becomes 5
3
Example run
Problem 3: The Sieve of Eratosthenes
Number of primes from 2 through 10000: 1229
Check. The count is 1229. The first prime, primes[0], is 2. The last prime, primes[primes.length - 1], is 9973. Print the first ten primes with a loop and compare with 2 3 5 7 11 13 17 19 23 29.
If you see ArrayIndexOutOfBoundsException: read the index in the message. An index of 10001 means a loop went one past the end of the checklist. An index equal to your count means next went past the end of primes.
Lab problem 4
Prime factorization
Loop through an array · Repeated division · Counter
Ask for an integer from 2 through 10000. Use your primes array from Problem 3 to print its prime factorization. Print one line for each prime that divides the number: the prime, a colon, and how many times it appears.
Example run
Problem 4: Prime factorization
Enter an integer from 2 through 10000:
132
Prime factorization of 132
2: 2
3: 1
11: 1
That output says 132 = 2 × 2 × 3 × 11.
Try it on paper first
Factor 132 by going through the primes in order. Keep dividing by a prime for as long as it divides evenly, then move to the next prime.
Prime
Divisions
Times it divided
Number left
2
132 ÷ 2 = 66, then 66 ÷ 2 = 33
2
33
3
33 ÷ 3 = 11
1
11
5
Does not divide 11
0
11
7
Does not divide 11
0
11
11
11 ÷ 11 = 1
1
1
Only the rows with a count above 0 are printed. When the number left reaches 1, the factorization is finished.
How to build it
Step 1. Read the number.
Print the prompt and read an integer with keyboard.nextInt(). Print the Prime factorization of line right away, before any dividing, because dividing changes the number.
Step 2. Loop through the primes.
Use a for loop that visits every box of primes. Inside the loop, primes[i] is the prime you are testing.
Step 3. Divide out one prime and count.
Inside the for loop, start a counter at 0. Then use a while loop: as long as the number is divisible by primes[i], divide the number by primes[i] and add one to the counter.
You have written this before. This step is Assignment 2, Activity 10. There the prime was typed in. Here it comes from primes[i], and the outer loop gives you the next prime automatically.
Where the counter goes. The counter must start at 0 again for every prime, so declare it inside the for loop and above the while loop.
Step 4. Print the primes that divided.
After the while loop ends, check the counter. If it is greater than 0, print the prime, a colon, and the counter.
Step 5. Stop when the number reaches 1.
Once the number left is 1, no other prime can divide it. Your program is correct whether or not the loop stops early. To stop early, add a second condition to the for loop so that it continues only while the number is greater than 1.
Check. Try these four inputs.
Input
Expected lines
What it tests
132
2: 2, 3: 1, 11: 1
Several primes, one repeated
1024
2: 10
One prime many times
9973
9973: 1
The last prime in your array
10000
2: 4, 5: 4
The largest allowed input
If nothing prints: make sure Problem 4 uses the same primes array that Problem 3 filled, and that Problem 3’s code comes first in main.
Before submitting
Fill in your name and date. Keep both solutions in ArrayLab.java.
Run the checks for Problem 3 and all four inputs for Problem 4.
Be ready to explain what struckOut[i] means and why Step 5 of the Sieve needs two position variables.