第10次实验课作业

实验课

第10次实验课需要提交作业
本次作业需提交： 第5章的程序设计题“10”、“13”
第5章程序设计补充题
以实验报告形式提交

【10】在公元前3世纪，古希腊天文学家埃拉托色尼发现了一种找出不大于n的所有自然数中的素数的算法，即埃拉托色尼筛选法。这种算法首先需要按顺序写出2～n中所有的数。以n＝20为例：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
然后把第一个元素画圈，表示它是素数，然后依次对后续元素进行如下操作：如果后面的元素是画圈元素的倍数，就画×，表示该数不是素数。在执行完第一步后，会得到素数2，而所有是2的倍数的数将全被画掉，因为它们肯定不是素数。接下来，只需要重复上述操作，把第一个既没有被圈又没有画×的元素圈起来，然后把后续的是它的倍数的数全部画×。本例中这次操作将得到素数3，而所有是3的倍数的数都被去掉。依次类推，最后数组中所有的元素不是画圈就是画×。所有被圈起来的元素均是素数，而所有画×的元素均是合数。编写一个程序实现埃拉托色尼筛选法，筛选范围是2～1000。

【13】编写一个程序，输入5个1位整数，例如：1、3、0、8、6，输出由这5个数字组成的最大的5位数。
要求：将输入的5个整数排序，然后按顺序组成一个万位的整数再输出。要求：要在一个数组里完成。

【补充题】输入一个整型数组然后排序，再输入一个整型数，要求按原来排序的规律将它插入数组中。
要求：要在一个数组里完成。

#include <iostream>
#include <cmath>
#include  <iomanip>
using namespace std;
void task1() {
  int i = 2;
  for (; i < 1001; i++) {
    int count = 0;
    for (int j = 2; j <= sqrt(i) && i >= j; j++) {
      if (i % j == 0) count++;
    }
    if (count < 2) cout<<setw(5)<<i;
  }
}
void task2() {
  int array[5];
  for (size_t i = 0; i < 5; i++) {
    cin>>array[i];
  }
  for ( int i = 0; i < 5 ; i++) {
        for ( int o = i+1 ;o < 5 ;o++) {
            if ( array[i] < array [o]) {
                int temp = array[i];
                array[i] = array[o];
                array[o] = temp;
            }
        }
    }
  for (size_t i = 0; i < 5; i++) {
    cout<<array[i];
  }
  cout<<endl;
}
void changedInsertionSort(int a[],int len) {
  int j = len-1;
  int key = a[j];
  int k = j -1;
  for (; k >= 0 && a[k] > key; k--) {
    a[k+1] = a[k];
  }
  a[k+1] = key;
}
void task3() {
  int a[100];
  int count = 0;
  bool flag = 1;
  while (flag) {
    int x;
    cin>>x;
    a[count] = x;
    count++;
    changedInsertionSort(a,count);
    for (int i = 0; i < count; i++) {
      cout<<a[i]<<'\t';
    }
    cout<<"press 1 to continue,press 0 to end.";
    cin>>flag;
  }
}
int main() {
  task3();
  return 0;
}