CS13002 PDS Lab, Spring 2003, Section 1/A

Solution of Assignment 4

1. [English sentences]
   
   This is a simple body-warming exercise. Look at the code below. It's more than self-explanatory. The only thing I would plan to mention in this regard is that I have never consulted the ASCII table for this code. C treats characters as integers. Therefore one can use the standard arithmetic routines on characters (like 'a'+i). Of course, I knew that `A' through `Z' come consecutively in the alphabetic order in the ASCII table and so do `a' through `z'.

   #include <stdio.h>
   
   int main ()
   {
      char sentence[1024];
      int count[26];
      int i, l;
   
      printf("Enter an English sentence :\n");
      fgets(sentence,1000,stdin);
      l = strlen(sentence);
      for (i=0; i<26; i++) count[i] = 0;
      for (i=0; i<l; i++) {
         if ((sentence[i] >= 'a') && (sentence[i] <= 'z'))
            count[sentence[i]-'a']++;
         else if ((sentence[i] >= 'A') && (sentence[i] <= 'Z'))
            count[sentence[i]-'A']++;
      }
      printf("The numbers of occurrences of the alphabetic letters in the sentence are :\n");
      for (l=i=0; i<26; i++) {
         printf("%c(%d)",'a'+i,count[i]);
         if (count[i]) l++;
         if (i%6==5) printf("\n");
      }
      printf("\nTotal number of distinct letters : %d\n",l);
   }
   

   The response of this program to the seventh sentence is as follows:

   Enter an English sentence :
   The quick brown fox jumps over a lazy dog.
   The numbers of occurrences of the alphabetic letters in the sentence are :
   a(2)b(1)c(1)d(1)e(2)f(1)
   g(1)h(1)i(1)j(1)k(1)l(1)
   m(1)n(1)o(4)p(1)q(1)r(2)
   s(1)t(1)u(2)v(1)w(1)x(1)
   y(1)z(1)
   Total number of distinct letters : 26
   

   This is a sentence containing all the letters of the English alphabet. Such a sentence is called a pangram or a holalphabetic sentence. This sentence is frequently used to test typing skills, becasue, well, because it is a pangram. A shorter pangram is The five boxing wizards jump quickly.
   
   
   
2. [The sieve of Eratosthenes]
   
   This is a straightforward program as the following (documented) code suggests:

   #include <stdio.h>
   #include <math.h>
   
   void doSieve ( char *A , int n )
   {
      int m, i, j;
   
      /* Initialize array */
      A[0] = A[1] = 1;               /* 0 and 1 are not primes */
      for (i=2; i<=n; i++) A[i] = 0; /* Unmark other entries, initially */
      i = 0;
      m = (int)sqrt((double)n);      /* Do this only once outside the loop */
      while (i <= m) {
         if (A[i] == 0) {            /* Find the next unmarked entry */
            j = 2 * i;
            while (j <= n) {
               A[j] = 1;             /* mark proper multiples of i */
               j += i;
            }
         }
         i++;
      }
   }
   
   void printPrime ( char *A , int n , int PCNo )
   {
      int i,j,k;
   
      j = 0;
      k = 1000000 + PCNo;
      for (i=2; i<=n; i++) {
         if (A[i] == 0) {            /* if i is prime */
            j++;
            if (j == k) {
               printf("%d-th prime is %d\n",j,i);
               return;
            }
         }
      }
      printf("The desired prime is not found. Increase n.\n");
   }
   
   int main ()
   {
      int n;
      char A[20000000];
      int PCNo = 128;
   
      printf("n = "); scanf("%d",&n); printf("%d\n",n);
      if (n <= 0) {
         fprintf(stderr, "Error: positive integer expected.\n");
         exit(1);
      }
      doSieve(A,n);                  /* Mark the composites */
      printPrime(A,n,PCNo);          /* Print the desired prime */
   }
   

   Two runs of the program with different values of n are shown below:

   n = 15000000
   The desired prime is not found. Increase n.
   n = 16000000
   1000128-th prime is 15487939
   

[Course home] [Home]