plz any one help me to solve this two proble befor 8/2/2008
plzzzzzzzzzzzzzzzzzzzzz helpe me >>>
Problem 1: Fermat’s Theorem
Program: fermat.cpp
Input: fermat.in
Output: fermat.out
Description
In a letter dated December 25, 1640; the great mathematician Pierre de Fermat wrote to Marin Mersenne that he just proved that an odd prime p is expressible as p = a2 + b2 if and only if p is expressible as p = 4c + 1. As usual, Fermat didn’t include the proof, and as far as we know, never wrote it down. It wasn’t until 100 years later that no one other than Euler proved this theorem. To illustrate, each of the following primes can be expressed as the sum of two squares:
5 = 22 + 12 13 = 32 + 22 17 = 42 +12 41= 52 + 42
Whereas the primes 11, 19, 23, and 31 cannot be expressed as a sum of two squares. Write a program to count the number of primes that can be expressed as sum of squares within a given interval.
Input Format
Your program will be tested on one or more test cases. Each test case is specified on a separate input line that specifies two integers L,U where L ≤U <1000000
The last line of the input file includes a dummy test case with both L = U = −1.
Output Format
For each test case, write the result using the following format:
L U x y
where L and U are as specified in the input. x is the total number of primes within the interval [L,U] (inclusive,) and y is the total number of primes (also within [L,U]) that can be expressed as a sum of squares.
Sample Input/Output
fermat.in
10 20
11 19
100 1000
-1 -1
Fermat.out
10 20 4 2
11 19 4 2
100 1000 143 69
Problem 2: A Tale from the Dark Side of The Moon
Program: pink.cpp
Input: pink.in
Output: pink.out
Saad: So why don’t you just recompile the program on the new hardware?
DS students: We cannot. We lost the source code.
Saad: How typical! What does the program do? Do you have any documentation?
DS students: The manual page does mention something about the documentation in the source code.
Saad: A manual page is good. What does it say?
DS students: Just one line: “See the source code for more information.”
Us: Argh! What do you know about the program?
DS students: Well, it seems to be taking simple text, similar to that found in an English dictionary, and printing it after some modification.
Saad: What kind of modification?
DS students: It removes any character that is not a lowercase letter. But not white spaces. White spaces are preserved as seen in the input.
Saad: Do you have a sample input/output?
DS students: Plenty. Here’s one. (see bottom of page.)
Saad: This is rather small! Did you try it on anything bigger?
DS students: It works on any text as long as the lines are less then eighty characters wide. It doesn’t seem to mind working on lengthy documents. But it does terminate once it sees the sequence "EOF" (without the double quotes.)
One student: Don’t forget to tell them about the "dd" thingy.
Saad : What "dd" thingy?
DS students: Whenever it sees a pair of small letter "d", one right after the other, it replaces them with "p".
Saad: Why?
DS students: Who knows? It just does that!
Saad: What about "ddd" and "dddd"? How does it behave then?
DS students: Where in English will you find a "dddd" or even a "ddd"? Haven’t you been listening?
Saad: Oops. We’ll pay more attention. Anything else?
Another student: There is also the "vv" thingy.
Saad: What about "vv"?
DS students: Every "vv" is replaced with a "m".
Yet another student: No, wait! That was a printer problem. it had nothing to do with the program. Remember?
DS students: Oh, that’s right. Forget about the "vv" thingy.
Saad: What about the "dd" thingy? Was that just a printer problem too?
DS students: No. That was the program.
Saad: What else?
DS students: One last thing. It seems to be replacing every "ei" with "ie".
Saad: Every one of them?
DS students: Except if it comes right after "c" then it remains as is.
Saad: Makes sense. That’s all, right?
DS students: No, we just remembered one more thing: It replaces the sequence "pink" with "floyd" anywhere in the text.
Saad: What?! Who wrote this program? Why do you need it in the first place?
DS students: We think it will increase our chances of getting A in the course if we get it right.
Saad: Yeah! Right.
Sample Input/Output
pink.in
unpinked is an 8 letter word. Honest!
vv is ok, d123d is ok, 123dd is not
i received mail from liechtenstein
.. ...adding means to imitat.#$!%%$e
EOF
Pink.out
unfloyded is an letter word onest
vv is ok dd is ok p is not
i received mail from liechtenstien
aping means to imitate
