Administrivia
• Please make sure you have obtained a Unix account.
• Lab #1 is due Wednesday (end of Wednesday at midnight). Usually, labs are due Friday midnight of the week they occur. It is especially important to set up your central reppository.
• If you decide not to take this course after all, please tell CalCentral ASAP, so that we can adjust the waiting list accordingly.
Copyright By PowCoder代写 加微信 powcoder
• HW #0 will be up this evening, due next Friday at midnight. While you get credit for any submission, we strongly suggest that you give the problems a serious try.
• We strongly discourage taking this course P/NP (or S/U).
Last modified: Fri Jan 24 14:29:30 2020 CS61B: Lecture #2 1
Lecture #2: Let’s Write a Program: Prime Numbers
Problem: want java Primes U to print prime numbers through U . You type: java Primes 101
Ittypes: 2357111317192329
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101
Definition: A prime number is an integer greater than 1 that has no divisors smaller than itself other than 1.
(Alternatively: p > 1 is prime iff gcd(p,x) = 1 for all 0 < x < p.)
Useful Facts:
• k ≤ √N iff N/k ≥ √N, for N,k > 0. • If k divides N then N/k divides N.
So: Try all potential divisors up to and including the square root.
Last modified: Fri Jan 24 14:29:30 2020 CS61B: Lecture #2 2
public class Primes {
/** Print all primes up to ARGS[0] (interpreted as an
* integer), 10 to a line. */
public static void main(String[] args) { printPrimes(Integer.parseInt(args[0]));
/** Print all primes up to and including LIMIT, 10 to * aline.*/
private static void printPrimes(int limit) {
/*{ For every integer, x, between 2 and LIMIT, print it if
isPrime(x), 10 to a line. }*/ }
/** True iff X is prime */
private static boolean isPrime(int x) { return /*( X is prime )*/;
Last modified: Fri Jan 24 14:29:30 2020
CS61B: Lecture #2 3
Testing for Primes
private static boolean isPrime(int x) { if (x <= 1)
return false;
return !isDivisible(x, 2); // "!" means "not" }
/** True iff X is divisible by any positive number >=K and < X, * givenK>1.*/
private static boolean isDivisible(int x, int k) { if (k >= x) // a “guard”
return false;
else if (x % k == 0) // “%” means “remainder”
return true;
else // if (k < x && x % k != 0)
return isDivisible(x, k+1); }
Last modified: Fri Jan 24 14:29:30 2020
CS61B: Lecture #2 4
Thinking Recursively
Understand and check isDivisible(13,2) by tracing one level.
/** True iff X is divisible by * some number >=K and < X, * givenK>1.*/
private static boolean isDivisible…
if (k >= x)
return false;
else if (x % k == 0)
return true;
return isDivisible(x, k+1); }
Lesson: Comments aid understanding. Make them count!
• Call assigns x=13, k=2
•Body has form ‘if(k>=x)S1
• Since 2 < 13, we evaluate the
first else.
• Checkif13mod2=0;it’snot.
• Left with isDivisible(13,3).
• Rather than tracing it, instead use the comment:
• Since 13 is not divisible by any integer in the range 3..12 (and 3 > 1), isDivisible(13,3) must be false, and we’re done!
• Sounds like that last step begs the question. Why doesn’t it?
Last modified: Fri Jan 24 14:29:30 2020
CS61B: Lecture #2 5
if ( ) return false;
else if (x % k == 0)
return true;
return isDivisible(x,
while( ) { if (x % k1 == 0)
return true;
r}eturn false;
Last modified: Fri Jan 24 14:29:30 2020
while ( ) { // if (x % k == 0)
return true;
// or k += 1, or (yuch) k++
}return false;
for( ; ; ){ if(x%k1==0)
• isDivisible is tail recursive, and so creates an iterative process.
• Traditional “Algol family” production languages have special syntax for iteration. Four equivalent versions of isDivisible:
int k1 = k;
int k1 = k
return true; }
return false;
CS61B: Lecture #2 6
Using Facts about Primes
• We haven’t used the Useful Facts from an earlier slide. Only have to check for divisors up to the square root.
• So, reimplement the iterative version of isDivisible:
/** True iff X is divisible by some number >=K and < X, * given that K > 1, and that X is not divisible by
* any number >1 and