C代写:CS109 A Little Light Number Theory

根据所给的公式,代写一个寻找完美数的程序。

Introduction

We are going to answer some simple but fundamental questions about the sequence of natural numbers N = 1, 2, 3, ... We are going to look at primality, composites and perfect numbers. Primes numbers are fundamental in mathematics and Computer Science, and perfect numbers are an interesting curiosity.
You will also be concerned with the execution time of your programs.

Prime Numbers

God may not play dice with the universe, but something strange is going on with the prime numbers.
- Paul Erdös

Prime numbers are among the most interesting of the natural numbers. A number p N is prime if it is evenly divisible by only 1 and p. The first prime number is 2, all primes except 2 must be odd, since all even numbers are divisible by 2. There are an infinity of primes, which was proven by Euclid about 300 B.C. There is no formula for finding the primes, but the prime number theorem tells us that the probability of a given m ∈ N, 1 < m ≤ N being prime is very close to 1 / lnN, since the number of primes less than N.

Composite Numbers

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic.
- Carl Friedrich Gauss

All natural numbers that are not prime are called composite. The fundamental theorem of arithmetic, also called the unique factorization theorem, states that every integer m ] 1 is either prime or a unique product of primes (p0, …, pk).

For example, 83736 = 2^33^21163. In 1801, the fundamental theorem of arithmetic was proved by Gauss in his book Disquisitiones Arithmetic.

Determining the prime factorization of m can be accomplished trying all primes p0, ..., pk ≤ m. The execution time is difficult to compute, since each successful division reduces the complexity, but is it bounded from above by O(log m), provided you have a list of primes to consult.

Perfect Numbers

Perfect numbers like perfect men are very rare.
- Rene Descartes

A perfect number is a natural number that is equal to the sum of its proper divisors.

For example, 1+2+3 = 6 and 496 = 1+2+4+8+16+31+62+124+248. The first four perfect numbers are 6, 28, 496 and 8128, and you will not find the next one until 33550336.

It is not known whether there are any odd perfect numbers, but it is considered unlikely. All even perfect numbers have the form 2^(p-1)(2^p-1) where p is prime and its digital root is 1.

Your Task

Your task is to go through each natural number beginning with 2 and determine whether it is prime (P), composite (C) or perfect (or E in honor of Euclid). Prime numbers cannot be factored, but you must perform a prime factorization of all composites. If you determine that a number is perfect, then you must list all of its proper divisors.

Consider the example given below. This shows the required format of the output.

2 P
3 P
4 C: 2 2
5 P
6 C: 2 3
6 E: 1 2 3
7 P
8 C: 2 2 2
9 C: 3 3
10 C : 2 5
11 P
12 C : 2 2 3
13 P
14 C : 2 7
15 C : 3 5
16 C : 2 2 2 2
17 P
18 C : 2 3 3
19 P
20 C : 2 2 5

What you should observe immediately is that you will need to store some quantities. You may want to store the prime factors of each composite. Is that necessary? You will need to store the store the proper divisors of a composite since you will not know that a number is perfect until you have tallied its proper divisors. The most obvious data structure for storing those divisors is an array.

Specifics

Writing the program using the nave approach of finding primes up to the value of a given number into order to find its prime factorization is, frankly, silly. You can and will do much better, and you will do so by using a sieve.

1
2
3
4
5
6
# ifndef _SIEVE
# define _SIEVE
# include "bv.h"

void sieve(bitV *) ; // Results in a vector of prime numbers
# endif

Your sieve will take as its sole argument a bit vector and it will mark with 1 the positions that correspond to a prime number, while all other positions will be marked 0.

A bit vector is a rarely taught but essential tool in the kit of all Computer Scientists and Engineers. Your bit vector implementation must match the given interface.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# ifndef _BVector
# define _BVector
# include <stdint.h>

typedef struct bitV {
uint8_t *vector;
uint32_t length;
} bitV;

bitV *newVec(uint32_t ); // Create a new vector of specified length

void delVec(bitV *); // Deletes a vector

void oneVec(bitV *); // Creates a vector of all 1

void setBit(bitV *, uint32_t); // Sets a specified bit

void clrBit(bitV *, uint32_t ); // Clears a specified bit

uint8_t valBit(bitV *, uint32_t ); // Returns the value of a specified bit

uint32_t lenVec (bitV *); // Return the length of the vector
# endif

The header file bv.h defines the exported type bitV and its associated operations. Even though C will not prevent you from directly manipulating the data structure, you must avoid the temptation and only use the functions defined in bv.h - no exceptions!

You must implement each of the functions specified in the header file. Most of them are just a line of two of C code, but their implementation can be subtle. You are warned again against using code that you may find on the Internet.

One could write a function

1
2
3
uint64_t nextPrime (uint64_t n) {
// Find the first prime after n
}

but that would be foolishness, even though the prime density is approximately ln1n . Instead, you will use a sieve. The easier to implement is the Sieve of Eratosthenes but ambitious students are encouraged to use a more sophisticated method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void sieve(bitV *v)
{

oneVec(v); // Assume all are prime
clrBit(v, 0); // 0 is, well, zero
clrBit(v, 1); // 1 is unity
setBit(v, 2); // 2 is prime
for (uint32_t i = 2; i <= sqrtl(lenVec(v)); i += 1)
{
if (valBit(v, i)) // It 's prime
{
for (uint32_t k = 0; (k + i) * i <= lenVec(v) ; k += 1)
{
clrBit(v, (k + i) * i ); // Its multiple are composite
}
}
}
return ;
}

Since you have been given the code for the Sieve of Eratosthenes, you must cite it and give proper credit if you use it. If, for example, you were to implement the Sieve of Sundaram, or the more modern Sieve of Atkin, you would not need to cite beyond the source of the algorithm and any pseudocode that you followed.

Submission

Your program must be capable of executing correctly until it would find the sixth perfect number. But, that would take a very long time unless you were very clever with your algorithms. So, your program will by default run until it reaches 100000. Along the way it should find four perfect numbers and a large number of prime numbers as well.

We will test your program by comparing its output with the output of a known correct program. Example output is given at the end of the assignment, and your program should match it exactly (for as far as the example goes, the test will go to 100 000).

You must turn in your assignment in the following manner:

  1. By default your program runs up through 100 000.
  2. Optionally, you can provide for ./parfait -n K were K is the largest natural number considered.
  3. Have file called Makefile that when the grader types make will compile your program. At this point you will have learned about make and can create your own Makefile.
    • CFLAGS=-Wall -Wextra -Werror -pedantic must be included.
    • CC=gcc must be specified.
    • make clean must remove all files that are compiler generated.
    • make should build your program, as should make all.
    • Your program executable must be named parfait.
  4. You program must have the source and header files:
    • bv.h to specify the bit vector operations and abstract data type bitV.
    • bv.c to implement the functionality.
    • sieve.h specifies the interface to the sieve.
    • sieve.c to implement the sieve algorithm of your choice.
    • parfait.c contains main() and may contain the other functions necessary to complete the assignment.
  5. You may have other source and header files, but do not try to be overly clever.
  6. A plain text file called README that describes how your program works.
  7. The executable file produced by the compiler must be called parfait.
  8. These files must be in the directory assignment1.
  9. You must commit and push the directory and its contents using git.