CS 1713

Introduction to Computer Programming II

Assignment 7

1. (100 pts) Write a program using linked lists to find prime numbers up to 1000 using the sieve method.

A prime number is a whole number greater than 1, whose only two whole-number factors are 1 and

itself. For example, 4 is not a prime number since its factors are 1,2 and 4. 7 is a prime number since

its factors are 1 and 7. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. You can

follow below steps to find the prime numbers

(a) Build a linked list consisting of integers 1 to 1000. You can use the following methods discussed

in the class for this step.

node *inserthead(node *head, int a)

node *inserttail(node *head, int a)

(b) Implement a method to delete all the multiples of an integer k (leave k in the list and remove 2k,

3k, . . .) from the linked list. These numbers (2k, 3k, . . .) can not be prime since they are divisible

by k and they are deleted from the list. This method returns the new list.

node *deletemultiples(node *head, int k)

Use this method to delete all the multiples of 2..32 from the linked list. You need to use deletemultiples method for each number from 2 to 32 to delete the multiples of that number.

(c) The remaining numbers will be prime numbers. Print the linked list to see the prime numbers.

The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29 and should be part of your

output.

(d) Free the linked list when you are done and use valgrind to check for memory leaks.

Submit your program electronically using the blackboard system

The program you submit should be your own work. Cheating will be reported to office of academic integrity.

Both the copier and copiee will be held responsible.