Conditionals: Prime Factorization

 

  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:
Screen Shot 2014-10-02 at 10.05.29 AM

Conditionals: The GCD

The GCD
Write a program GCD_YI.java that finds the greatest common divisor of two integers using the Euclidean Algorithm:

if x > y, then if y divides x, the gcd of x and y is y; otherwise, the gcd of x and y is the same as the gcd of x % y and y

On paper do an example (it can be the one from Khan Academy) but showing all the mathematical step but thinking the way you would write it as a program.

screen-shot-2016-10-17-at-12-02-56-pm

 

Conditionals: Sum of Squares

 

screen-shot-2016-10-27-at-8-36-29-am

A positive integer n is called squarefree, if no square of a prime divides n, thus 1, 2, 3, 5, 6, 7, 10, 11 are squarefree, but not 4, 8, 9, 12.

Consider equations of the form: a2 + b2 = N, 0 ≤ a ≤ b, a, b and N integer.

For N=65 there are two solutions:

a=1, b=8 and a=4, b=7.

We call S(N) the sum of the values of a of all solutions of a2 + b2 = N, 0 ≤ a ≤ b, where a, b and N  are integers.

Thus S(65) = 1 + 4 = 5.

Find ∑S(N), for all squarefree N only divisible by primes of the form 4k+1 with 4k+1 < 150.

Conditionals: Counting Sundays

screen-shot-2016-10-27-at-8-36-29-am

Counting Sundays

Problem 19

You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Conditionals: RGB to CMYK

Type conversion and conditionals. Several different formats are used to represent color. For example, the primary format for LCD displays, digital cameras, and web pages, known as the RGB format, specifies the level of red (R), green (G), and blue (B) on an integer scale from 0 to 255. The primary format for publishing books and magazines, known as the CMYK format, specifies the level of cyan (C), magenta (M), yellow (Y), and black (K) on a real scale from 0.0 to 1.0.

Write a program RGBtoCMYK_YI.java that converts RGB to CMYK. Prompt the user with messages for three integers red, green, and blue, and print the input red, green, and blue, then print the equivalent CMYK, {C,M,Y,K} values using the formulas in the attached image.
More details on edmodo.com
Project 1 # 2: RGB to CMYK

Conditionals: 1000 digit Number

 

screen-shot-2016-10-27-at-8-36-29-am

Project Euler Problem 8

Largest product in a series
The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Write a java program, ThirteenAdj_YI.java to find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

NOTE: Here is the code to handle the 1000-digit number

String adjStrNumbers = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
System.out.println("The length of this number is " + adjStrNumbers.length());
//The length of this number is 1000

Check what this code snippet does:

for ( int i = 0; i < 20; i++)
System.out.print( Integer.parseInt( adjStrNumbers.substring(i,i+1) ) );

WARNING:
The largest product of thirteen adjacent digits is 23514624000 if you declare the variables for product and largest of type “long”. Otherwise, when using type “int”, the largest product of thirteen adjacent digits is 2091059712 if you use int for x and product!!!!!!!!! THIS IS THE WRONG ANSWER

Conditionals: Relative prime numbers

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.

screen-shot-2016-10-17-at-11-16-58-am

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 *   *       *   *   *   *       *   *   
> 
*/

Event: Competition – picoCTF

What is picoCTF?

picoCTF is a free computer security game with original educational content built on a capture-the-flag framework created by security and privacy experts at Carnegie Mellon University.

Gain access to a safe and unique hands-on experience where participants must reverse engineer, break, hack, decrypt, and think creatively and critically to solve the challenges and capture the flags.

Sign up now and explore picoCTF’s newest features where you can build skills in the picoGym and read about cybersecurity terminology and principles with the picoPrimer.