ZuoTi.Pro
Question

#include <assert.h> #include <stdio.h> #include <stdlib.h> // initialize_array is given an array "arr" of "n" elements....

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
// initialize_array is given an array "arr" of "n" elements.
// It initializes the array by setting all elements to be "true" (any non-zero value).
void
initialize_array(int *arr, int n)
{
// TODO: Your code here.
assert(0);
}
// mark_multiples is given an array "arr" of size n and a (prime) number "p" less than "n"
// It assigns "false" (the zero value) to elements at array indexes 2*p, 3*p, 4*p,.., x*p (where x*p <= n-1)
// For example, given arr=[1, 1, 1, 1, 1, 1], n = 6 and p = 2
// mark_multiples set arr=[1, 1, 1, 1, 0, 1]
void
mark_multiples(int *arr, int n, int p)
{
// TODO: Your code here.
assert(0);
}
// prime_number_sieves finds all prime numbers less than n by constructing a "sieve of Eratosthenes"
// https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
// A pre-allocated, un-initialized, array "arr" of "n" elements is passed to the function
// When the function returns, the element at index i of "arr" should be "true" (any non-zero value) if i is a prime,
// and "false" (the zero value) if i is a composite number
// You need not care about the values of the 0-th and 1-st elements.
// You are expected to use the previous two functions, initialize_array and mark_multiples
//
// For example, given arr with n=6, the resulting sieve should be arr=[*, *, 1, 1, 0, 1]
// "*" means the corresponding element can be either 0 or 1. The seive at indexes 2,3,5 are marked "1"
// because 2,3,5 are primes
void
prime_number_sieves(int *arr, int n)
{
// TODO: Your code here
assert(0);
}
/* find_smallest_divisor finds the smallest prime divisor (>1) of "n". It assigns the value
* of the smallest divisor to the integer variable pointed to by "divisor".
* If "n" is a non-prime, the function returns true. Otherwise (i.e. "n" is a prime number),
* the function returns false. For example, in the following code snippet:
int d;
ret = find_smallest_divisor(21, &d)
//ret should contains "true" and d should be 3
You are expected to first use prime_number_sieves to first find all primes smaller than n.
Then, test if any prime found by prime_number_sieves divide n and return the smallest one.
Note that you'll need to allocate the integer array to pass to prime_number_sieves.
*/
int
find_smallest_divisor(int n, int *divisor)
{
// TODO: Your code here
assert(0);
}
engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

/* Please comment for any changes in program code */

#include <assert.h>

#include <stdio.h>

#include <stdlib.h>

// initialize_array is given an array "arr" of "n" elements.

// It initializes the array by setting all elements to be "true" (any non-zero value).

void initialize_array(int *arr, int n)

{

for (int i = 0; i < n; ++i) {

arr[i] = 1;

}

//assert(0);

}

// mark_multiples is given an array "arr" of size n and a (prime) number "p" less than "n"

// It assigns "false" (the zero value) to elements at array indexes 2*p, 3*p, 4*p,.., x*p (where x*p <= n-1)

// For example, given arr=[1, 1, 1, 1, 1, 1], n = 6 and p = 2

// mark_multiples set arr=[1, 1, 1, 1, 0, 1]

void mark_multiples(int *arr, int n, int p)

{

int i = 2;

while (i * p < n) {

arr[i * p] = 0;

++i;

}

//assert(0);

}

// prime_number_sieves finds all prime numbers less than n by constructing a "sieve of Eratosthenes"

// https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

// A pre-allocated, un-initialized, array "arr" of "n" elements is passed to the function

// When the function returns, the element at index i of "arr" should be "true" (any non-zero value) if i is a prime,

// and "false" (the zero value) if i is a composite number

// You need not care about the values of the 0-th and 1-st elements.

// You are expected to use the previous two functions, initialize_array and mark_multiples

//

// For example, given arr with n=6, the resulting sieve should be arr=[*, *, 1, 1, 0, 1]

// "*" means the corresponding element can be either 0 or 1. The seive at indexes 2,3,5 are marked "1"

// because 2,3,5 are primes

void prime_number_sieves(int *arr, int n)

{

// TODO: Your code here

initialize_array(arr, n);

int i = 2;

while (i < n) {

if (arr[i] != 0) {

mark_multiples(arr, n, i);

}

++i;

}

//assert(0);

}

/* find_smallest_divisor finds the smallest prime divisor (>1) of "n". It assigns the value

* of the smallest divisor to the integer variable pointed to by "divisor".

* If "n" is a non-prime, the function returns true. Otherwise (i.e. "n" is a prime number),

* the function returns false. For example, in the following code snippet:

int d;

ret = find_smallest_divisor(21, &d)

//ret should contains "true" and d should be 3

You are expected to first use prime_number_sieves to first find all primes smaller than n.

Then, test if any prime found by prime_number_sieves divide n and return the smallest one.

Note that you'll need to allocate the integer array to pass to prime_number_sieves.

*/

int find_smallest_divisor(int n, int *divisor)

{

// TODO: Your code here

int *array = new int[n];

int i;

prime_number_sieves(array, n);

for (i = 2; i < n; ++i) {

if (array[i] != 0) {

if (n % i == 0) {

*divisor = i;

return 1;

}

}

}

return 0;

//assert(0);

}

/* main to test our function implementation*/

int main() {

int divisor;

int number = 21;

bool test = find_smallest_divisor(number, &divisor);

if (test) {

printf("Smallest divisor of %d is %d\n", number, divisor);

}

else {

printf("%d is composite\n", number);

}

return 0;

}

//Sample output

0 0
Add a comment
Know the answer?
Add Answer to:
#include <assert.h> #include <stdio.h> #include <stdlib.h> // initialize_array is given an array "arr" of "n" elements....
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • #include <sys/types.h> #include <sys/ipc.h> #include <sys/shm.h> #include <sys/wait.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include<time.h> void...

    #include <sys/types.h> #include <sys/ipc.h> #include <sys/shm.h> #include <sys/wait.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include<time.h> void insertionSort(int arr[], int n); void merge(int a[], int l1, int h1, int h2); void mergeSort(int a[], int l, int h) { int i, len=(h-l+1); //Using insertion sort for small sized array if (len<=5) { insertionSort(a+l, len); return; } pid_t lpid,rpid; lpid = fork(); if(lpid<0) { //Lchild proc not created perror("Left Child Proc. not created\n"); _exit(-1); } else if (lpid==0) { mergeSort(a,l,l+len/2-1); _exit(0); } else...

  • Write a C Program that inputs an array of integers from the user along-with the length...

    Write a C Program that inputs an array of integers from the user along-with the length of array. The program then prints out the array of integers in reverse. (You do not need to change (re-assign) the elements in the array, only print the array in reverse.) The program uses a function call with array passed as call by reference. Part of the Program has been given here. You need to complete the Program by writing the function. #include<stdio.h> void...

  • Consider the syntactically correct C code below, which is missing a function copy_positive. #include <stdio.h> /*...

    Consider the syntactically correct C code below, which is missing a function copy_positive. #include <stdio.h> /* copy_positive(A, Aout, size) * Given an array A, which will have the provided size, copy all positive * (non-negative/non-zero) elements of A into the provided output array Aout. * Return the size of the resulting array. */ /* (your code from below would be placed here) */ void print_array(int arr[], int n){ for( int i = 0; i < n; i++ ) printf("%d ",...

  • sort.c #include <stdlib.h> #include <stdio.h> #include "libsort.h" int main() {     int* array;     int size,...

    sort.c #include <stdlib.h> #include <stdio.h> #include "libsort.h" int main() {     int* array;     int size, c;     float median;     printf("Enter the array size:\n");     scanf("%d", &size);     array = (int*) malloc(size * sizeof(int));     printf("Enter %d integers:\n", size);     for (c = 0; c < size; c++)         scanf("%d", &array[c]);     sort(array, size);     printf("Array sorted in ascending order:\n");     for (c = 0; c < size; c++)         printf("%d ", array[c]);     printf("\n");     median = find_median(array,...

  • Deleting multiples of a given integer from a linked list: #include <stdio.h> #include <stdlib.h> #include <assert.h>...

    Deleting multiples of a given integer from a linked list: #include <stdio.h> #include <stdlib.h> #include <assert.h> #define MAX 10000 typedef struct node_tag { int v; // data struct node_tag * next; // A pointer to this type of struct } node; // Define a type. Easier to use. node * create_node(int v) { node * p = malloc(sizeof(node)); // Allocate memory assert(p != NULL); // you can be nicer // Set the value in the node. p->v = v; p->next...

  • Given the prototype: int countPassing(double arr[], int num); Assume that array arr contains num elements with...

    Given the prototype: int countPassing(double arr[], int num); Assume that array arr contains num elements with a value. You may assume that the array has been declared with at least num elements. Write the the function definition including the function header for countPassing() so that the number of values greater than or equal to 69.5 in arr[] is returned.

  • JAVA Objectives: 1. Apply linear search algorithm 2. Apply select sort algorithm 3. Apply array iteration...

    JAVA Objectives: 1. Apply linear search algorithm 2. Apply select sort algorithm 3. Apply array iteration skill Problem description: Write the following eight methods and write a main function to test these methods // return the index of the first occurrence of key in arr // if key is not found in arra, return -1 public static int linearSearch(int arr[], int key) // sort the arr from least to largest by using select sort algorithm public stati void selectSort(int arr[])...

  • Consider the following code C++ like program: int i, j, arr[5]; //arr is an array starting...

    Consider the following code C++ like program: int i, j, arr[5]; //arr is an array starting at index 0 void exchange(int x, int y) { int temp:= x; x:= y; y:= temp; } main(){ for (j = 0; j < 5; j++) arr[j]:= j; i:= 1; exchange(i, arr[i+1]); output(i, arr[2]); //print i and arr[2] } What is the output of the code if both parameters in function swapping are passed by: a- value? b- reference? c- value-result?

  • #include<stdio.h> #include<stdio.h> int main(){ int i; //initialize array char array[10] = {“Smith”, “Owen”, “Kowalczyk”, “Glass”, “Bierling”,...

    #include<stdio.h> #include<stdio.h> int main(){ int i; //initialize array char array[10] = {“Smith”, “Owen”, “Kowalczyk”, “Glass”, “Bierling”, “Hanenburg”, “Rhoderick”, “Pearce”, “Raymond”, “Kamphuis”}; for(int i=0; i<8;i++){ for(int j=0; j<9; j++){ if(strcmp(array[j],array[j+1])>0){ char temp[20]; strcpy(temp,array[j]); strcpy(array[j],array[j+1]); strcpy(array[j+1],temp); } } } printf(“---------File Names---------\n”); for(inti=0; i<9; i++){ printf(“\t%s\n”,array[i]); } printf(-------5 Largest Files according to sorting----\n”); for(int i=0;i>=5;i--) { printf(“\t%s\n”,array[i]); } return0; } Consider the "sort" program (using with void* parameters in the bubblesort function) from the week 10 "sort void" lecture. Modify it as follows...

  • In the blank below, write the contents of array arr after the following code is executed...

    In the blank below, write the contents of array arr after the following code is executed up to the comment indicated in the main procedure below? #include <iostream> #include <algorithm> using namespace std; void do something(int list[], const int size); int main() { const int SIZE(10); int arr[SIZE] = { 5, 8, 1, 7, 3, 9, 4, 6, 10, 2 }; do somethingCarr, SIZE); ** Write the contents of array arr in the space below when execution reaches here. */...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT