Project Euler Problem 6

Sum square difference
The sum of the squares of the first ten natural numbers is,

1^2 + 2^2 + … + 10^2 = 385
The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)^2 = 55^2 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

1. Draw a flow chart for the Factors.java program. Here is an example of a flowchart with all the shapes your flow chart should have:

Another good flowchart example:

You can draw flowcharts if you create an account here

1. Tracing 101: Draw (on paper or doc ) a table of values for the variables “factor” and “n” for the following test data:

• A table for input: 27
• A table for input: 42
• A table for input: 29

 
3. Modify Factors.java to print just one copy of each of the prime divisors. ModFactors_YI.java

 
[spoiler title=’Factors.java’]

/******************************************************************************
 *  Compilation:  javac Factors.java
 *  Execution:    java Factors n
 *  
 *  Computes the prime factorization of n using brute force.
 *
 *   % java Factors 81
 *   The prime factorization of 81 is: 3 3 3 3 
 *
 *   % java Factors 168
 *   The prime factorization of 168 is: 2 2 2 3 7
 *
 *   % java Factors 4444444444
 *   The prime factorization of 4444444444 is: 2 2 11 41 271 9091 
 *
 *   % java Factors 4444444444444463
 *   The prime factorization of 4444444444444463 is: 4444444444444463
 * 
 *   % java Factors 10000001400000049
 *   The prime factorization of 10000001400000049 is: 100000007 100000007 
 *
 *   % java Factors 1000000014000000049
 *   The prime factorization of 1000000014000000049 is: 1000000007 1000000007
 *
 *   % java Factors 9201111169755555649
 *   The prime factorization of 9201111169755555649 is: 3033333343 3033333343 
 *
 *   Can use these for timing tests - biggest 3, 6, 9, 12, 15, and 18 digit primes
 *   % java Factors 997
 *   % java Factors 999983
 *   % java Factors 999999937
 *   % java Factors 999999999989
 *   % java Factors 999999999999989
 *   % java Factors 999999999999999989
 *
 *   Remarks
 *   -------
 *   - Tests factor*factor <= n instead of factor <= n for efficiency.
 *
 *   - The last two examples still take a few minutes.
 *
 ******************************************************************************/

public class Factors {

    public static void main(String[] args) { 

        // command-line argument
        long n = Long.parseLong(args[0]);

        System.out.print("The prime factorization of " + n + " is: ");

        // for each potential factor
        for (long factor = 2; factor*factor <= n; factor++) {

            // if factor is a factor of n, repeatedly divide it out
            while (n % factor == 0) {
                System.out.print(factor + " "); 
                n = n / factor;
            }
        }

        // if biggest factor occurs only once, n > 1
        if (n > 1) System.out.println(n);
        else       System.out.println();
    }
}

[/spoiler]

Click on this label:

Relative prime numbers

Write a program, RelativelyPrime_YI.java to prompt the user for an integer, n. The program displays an n-by-n table such a that there is an * in row i and column j if the gcd of i and j is 1 ( i and j are relatively prime) and a space in that position otherwise.

Hint: use GCD_YI.java to finds the greatest common divisor of two integers

Example output:

>run ca_relativelyprime 2 20
   1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 
 1 * * * * * * * * * * * * * * * * * * * * 
 2 *   *   *   *   *   *   *   *   *   *   
 3 * *   * *   * *   * *   * *   * *   * * 
 4 *   *   *   *   *   *   *   *   *   *   
 5 * * * *   * * * *   * * * *   * * * *   
 6 *       *   *       *   *       *   *   
 7 * * * * * *   * * * * * *   * * * * * * 
 8 *   *   *   *   *   *   *   *   *   *   
 9 * *   * *   * *   * *   * *   * *   * * 
10 *   *       *   *   *   *       *   *   
11 * * * * * * * * * *   * * * * * * * * * 
12 *       *   *       *   *       *   *   
13 * * * * * * * * * * * *   * * * * * * * 
14 *   *   *       *   *   *   *   *   *   
15 * *   *     * *     *   * *   * *   *   
16 *   *   *   *   *   *   *   *   *   *   
17 * * * * * * * * * * * * * * * *   * * * 
18 *       *   *       *   *       *   *   
19 * * * * * * * * * * * * * * * * * *   * 
20 *   *       *   *   *   *       *   *   
> 
*/