2

assignment-2.pdf

Introduction to Computer Science

Assignment 2

Exercise 1

Accompanying this assignment, you will find a C source code file sieve_of_erathostenes.c​. This file contains a partial implementation of a C program that computes all prime numbers up to a user-provided number \(n\), using the Sieve of Eratosthenes approach; the approach consists of:

1. Construct the sequence \(2, 3, \dots, n\) of all natural numbers between \(2\) and \(n\).

2. Pick the first “untreated” element \(i\) in the sequence (initially, \(2\)).

3. Mark \(i\) as a prime number.

4. Mark all multiples of \(i\) as composite (non-prime).

5. Repeat steps 2-4 until all elements have been treated.

Your task is to complete this implementation, using an array of integers to store the results of treating the numbers in the sequence. We suggest using:

• ​0​ to indicate that the number (the index) has not been treated yet,
• A negative number to indicate that the corresponding number is composite,
• A positive number to indicate the number is a prime number.

The program must print the resulting numbers using color codes:

• Green for prime numbers,
• Red for non-prime numbers,
• Separating the numbers in the sequence with commas.

/*
 * This program reads a positive number n, and prints on the screen
 * all the numbers in the range 1..n, indicating for each if it is a 
 * prime number or not, using color codes: green for primes, red for
 * non-primes. 
 * The program uses the process known as the Sieve of Erathostenes to
 * distinguish between prime numbers and composite numbers. 
 * TODO Implement the whole program below. Import libraries above if 
 * necessary.
 */
#include<stdio.h>

#define green "\x1b[32m"
#define red "\x1b[31m"
#define defaul "\x1b[39m"

int main() {
    int n;

    //determine whether the input is valid
    do {
        printf("Please enter a positive number: ");
        scanf("%d", &n);
    } while(n <= 0);

    int digit = n - 1; // means how many numbers are there in the array

    //define and store the sequence from 2 to n
    int original_sequence[digit];
    for(int i = 0; i < digit ; i++) {
        original_sequence[i] = i + 2;
    }

    //define category array to categorize the number and set its value to -1 means "untreated"
    // 1 means corresponding number is prime, 0 is composite 
    int category[digit];
    for (int l = 0; l < digit; l++) {
        category[l] = -1; 
    }

    //find the first untreated number and set its category to 1
    int untreated_number;
    for(int k = 0; k < digit; k++) { 
        if(category[k] == -1) {
            untreated_number = original_sequence[k];
            category[k] = 1;

            //find the multiple of untreated_number and set its category to 0
            for(int j = k + 1; j < digit; j++) {
                if(original_sequence[j] % untreated_number == 0)//if the number is the multiple
                    category[j] = 0;//set to 0 (composite)
            }
        }
    }

    //output the array with the reference of category
    for(int m = 0; m < digit; m++) {
        if(category[m] == 1)//if number is prime
            printf("%s%d%s,", green, original_sequence[m], defaul);
        else
            printf("%s%d%s,", red, original_sequence[m], defaul);
    } 
    printf("\n");
    return 0;
}

---

Exercise 2

Accompanying this assignment, you will find a C source code file caesar_encrypt.c​. This file contains a partial implementation of a program in C, that receives as input from standard input, a string of characters. The program then:

• Computes a number \(n\) by adding up all the ASCII codes of the first line of the input (excluding the newline character terminating the first line). If the line has more than 80 characters long, the number \(n\) will be composed by adding up all the ASCII codes of the first 80 characters.
• The number \(n\) is used as the seed to generate a pseudo-random number \(x\), in the interval \([0, 255]\).
• The program outputs a string of characters where each character \(c\) from the input, whose ASCII code is \(a\), is replaced by the character with ASCII code \((a + x) \% 128\).
• After the text, the program outputs the number \(n\), using the following format: <seed>n</seed>​. For instance, if the number \(n\) is \(7\), the program must output as the last line, after the encoded text, the line <seed>7</seed>​.

/*
 * This program reads text from standard input, and performs the 
 * following tasks:
 * - Computes a number n summing up all the ASCII codes of the first
 *   line, or the first 80 characters of the first line, if the line
 *   is longer than 80 characters.
 * - Uses n as a seed to generate a pseudo-random number x in the range
 *   [0, 255].
 * - Uses x to encrypt every character of the input, including the
 *   first line characters, as follows: for every character c, if 
 *   the ASCII code of c is a, then the program has to output the
 *   character with code (a + x) % 128.
 *   After the encrypted text, the program must output, in a separate
 *   line, the seed n using the following format:
 *   <seed>n</seed>
 *   where n is the seed. 
 * TODO Implement the whole program below. Import libraries above if 
 * necessary.
 */
#include<stdio.h>
#include<stdlib.h>

#define maxinput 1024 

int main() {
    int ch;
    int character[maxinput]; //define an array to store the character
    int n = 0; // n = ascii sum
    int character_amount = 1; //define the number of character inputting

    ch = getchar(); //receive the first character

    //calculate n, use breakline to stop inputting, and if character_amount > 80, 
    //then stop calculating sum. But still store it in the array
    while(ch != '\n') {
        if(character_amount <= 80) {
            n += ch;
        }
        character[character_amount - 1] = ch;
        character_amount += 1;
        ch = getchar();
    }

    //generate the seed and calculate x
    srand(n);
    int x = rand() % 256;

    //print and encrypt the text
    for(int i = 0; i < character_amount - 1; i++) {
        int encrypted_ch;
        encrypted_ch = (character[i] + x) % 128;
        printf("%c", encrypted_ch);
    }

    //print the seed
    printf("\n<seed>%d</seed>\n", n);

    return 0;
}