Печать простых чисел от 1 до 100

Question

Этот код c ++ выводит следующие простые числа: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97.

Но я не думаю, что моя книга так хочет, чтобы ее писали. Здесь упоминается кое-что о квадратном корне числа. Поэтому я попытался изменить свой второй цикл на for (int j=2; j<sqrt(i); j++), но он не дал мне нужного результата.

Как мне нужно изменить этот код так, как того хочет моя книга?

int main () 
{
    for (int i=2; i<100; i++) 
        for (int j=2; j<i; j++)
        {
            if (i % j == 0) 
                break;
            else if (i == j+1)
                cout << i << " ";

        }   
    return 0;
}

Простое целое число - это число, которое имеет ровно два разных делителя, а именно 1 и сам номер. Написать, запустить и протестировать программу на C ++, которая находит и печатает все простые числа меньше 100. (Подсказка: 1 - простое число число. Для каждого числа от 2 до 100 найти остаток = число% n, где n колеблется от 2 до sqrt (число). \ Если н больше, чем sqrt (число), число не делится поровну на п. Зачем? Если какой-либо остаток равен 0, число не является простым числом.)

Answer 1

Три способа:

1

int main () 
{
    for (int i=2; i<100; i++) 
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
                break;
            else if (j+1 > sqrt(i)) {
                cout << i << " ";

            }

        }   

    return 0;
}

2

int main () 
{
    for (int i=2; i<100; i++) 
    {
        bool prime=true;
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
            {
                prime=false;
                break;    
            }
        }   
        if(prime) cout << i << " ";
    }
    return 0;
}

3.

#include <vector>
int main()
{
    std::vector<int> primes;
    primes.push_back(2);
    for(int i=3; i < 100; i++)
    {
        bool prime=true;
        for(int j=0;j<primes.size() && primes[j]*primes[j] <= i;j++)
        {
            if(i % primes[j] == 0)
            {
                prime=false;
                break;
            }
        }
        if(prime) 
        {
            primes.push_back(i);
            cout << i << " ";
        }
    }

    return 0;
}

Редактировать: В третьем примере мы отслеживаем все наши ранее вычисленные простые числа. Если число делится на не простое число, существует также некоторый простой <= тот делитель, на который он также делится. Это уменьшает вычисления на коэффициент primes_in_range / total_range. </p>

Answer 2

Если j равно равно sqrt(i), это также может быть допустимым фактором, не только если он меньше .

Чтобы выполнить итерации вплоть до sqrt(i) во внутреннем цикле, вы можете написать:

for (int j=2; j*j<=i; j++)

(по сравнению с использованием sqrt(i) преимущество заключается в том, что не требуется преобразование в числа с плавающей запятой.)

Answer 3

Если число имеет делители, хотя бы один из них должен быть меньше или равен квадратному корню из числа. Когда вы проверяете делители, вам нужно проверять только квадратный корень, а не все проверяемое число.

Answer 4

Это моя очень простая программа на С ++, в которой перечисляются простые числа от 2 до 100.

for(int j=2;j<=100;++j)
{
    int i=2;
    for(;i<=j-1;i++)
    {
        if(j%i == 0)
            break;
    }

    if(i==j && i != 2)
        cout<<j<<endl;
}

Answer 5

Используя Сито Эратосфена * Логика 1002 *, я могу достичь тех же результатов с намного быстрее скорость.

Мой код демо VS принятый ответ .

Сравнение count, мой код требует значительно меньше итераций, чтобы закончить работу. Проверьте результаты для различных значений N в конце.

Почему этот код работает лучше, чем уже принятые:

- четные числа не проверяются ни разу на протяжении всего процесса.

- и внутренние, и внешние петли проверяют только в возможных пределах. Никаких посторонних проверок.

Код:

int N = 1000; //Print primes number from 1 to N
vector<bool> primes(N, true);
for(int i = 3; i*i < N; i += 2){    //Jump of 2
    for(int j = 3; j*i < N; j+=2){  //Again, jump of 2
        primes[j*i] = false;
    }
}
if(N >= 2) cout << "2 ";
for(int i = 3; i < N; i+=2){        //Again, jump of 2
    if(primes[i] == true) cout << i << " "; 
}

Для N = 1000 мой код занимает 1166 итераций, принятый ответ - 5287 (в 4,5 раза медленнее)

Для N = 10000 мой код занимает 14637 итераций, принятый ответ - 117526 (в 8 раз медленнее)

Для N = 100000 мой код занимает 175491 итераций, принятый ответ - 2745693 (в 15,6 раз медленнее)

Answer 6

на самом деле лучшее решение состоит в том, чтобы использовать «простое сито или простое число», которое «является быстрым типом алгоритма для поиска простых чисел» .. wikipedia

Простой (но не более быстрый) алгоритм называется «сито эратосфена» и может быть выполнен в следующие шаги (снова из Википедии):

1. Создать список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n).
2. Первоначально пусть p равно 2, первому простому числу.
3. Начиная с p, посчитайте с шагом p и отметьте каждое из этих чисел больше, чем само p в списке. Эти цифры будут 2р, 3р, 4р и т.д .; обратите внимание, что некоторые из них, возможно, уже отмечены.
4. Найдите первое число больше p в списке, который не помечен. Если такого номера не было, остановитесь. В противном случае, пусть р теперь равно это число (которое является следующим простым) и повторите с шага 3.

Answer 7

Поиск простых чисел до 100 особенно приятен и прост:

    printf("2 3 ");                        // first two primes are 2 and 3
    int m5 = 25, m7 = 49, i = 5, d = 4;
    for( ; i < 25; i += (d=6-d) )
    {
        printf("%d ", i);                  // all 6-coprimes below 5*5 are prime
    }
    for( ; i < 49; i += (d=6-d) )
    {
        if( i != m5) printf("%d ", i);
        if( m5 <= i ) m5 += 10;            // no multiples of 5 below 7*7 allowed!
    }
    for( ; i < 100; i += (d=6-d) )         // from 49 to 100,
    {
        if( i != m5 && i != m7) printf("%d ", i);
        if( m5 <= i ) m5 += 10;            //   sieve by multiples of 5,
        if( m7 <= i ) m7 += 14;            //                       and 7, too
    }

Квадратный корень из 100 равен 10 , и поэтому это исполнение сита Эратосфена с 2-3 wheel использует кратные только простые числа выше 3 , которые не больше чем 10 - а именно. 5 и 7 в одиночку! - просеивать 6 -кримы ниже 100 в пошаговом режиме.

Answer 8

Можно изменить цикл for на for (int j=2; j<=sqrt(i); j++), но тогда вам также нужно изменить что-то еще. Смотря конкретно на ваше состояние печати,

else if (i == j+1) {
      cout << i << " ";
}

почему это никогда не сработает, если вы только итерируете до sqrt(i)? Куда вы можете переместить cout, чтобы изменить это? (Подсказка: вы можете переместить печать из цикла, а затем использовать переменную какого-либо типа флага)

Answer 9

Я проверяю, является ли число простым или нет, используя следующий код (конечно, используя sqrt):

bool IsPrime(const unsigned int x)
{
  const unsigned int TOP
  = static_cast<int>(
      std::sqrt( static_cast<double>( x ) )
    ) + 1;

  for ( int i=2; i != TOP; ++i )
  {
    if (x % i == 0) return false;
  }
  return true;
}

Я использую этот метод для определения простых чисел:

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <cmath>

void initialize( unsigned int *, const unsigned int );
void show_list( const unsigned int *, const unsigned int );
void criba( unsigned int *, const unsigned int );
void setItem ( unsigned int *, const unsigned int, const unsigned int );

bool IsPrime(const unsigned int x)
{
  const unsigned int TOP
  = static_cast<int>(
      std::sqrt( static_cast<double>( x ) )
    ) + 1;

  for ( int i=2; i != TOP; ++i )
  {
    if (x % i == 0) return false;
  }
  return true;
}

int main()
{

    unsigned int *l;
    unsigned int n;

    cout << "Ingrese tope de criba" << endl;
    cin >> n;

    l = new unsigned int[n];

    initialize( l, n );

    cout << "Esta es la lista" << endl;
    show_list( l, n );

    criba( l, n );  

    cout << "Estos son los primos" << endl;
    show_list( l, n );
}

void initialize( unsigned int *l, const unsigned int n)
{
    for( int i = 0; i < n - 1; i++ )
        *( l + i ) = i + 2;
}

void show_list( const unsigned int *l, const unsigned int n)
{
    for( int i = 0; i < n - 1; i++ )
    {
        if( *( l + i ) != 0)
            cout << l[i] << " - ";
    }
    cout << endl;
}

void setItem( unsigned int *l, const unsigned int n, const unsigned int p)
{
    unsigned int i = 2;
    while( p * i <= n)
    {
        *( l + (i * p - 2) ) = 0;
        i++;
    }
}

void criba( unsigned int *l, const unsigned int n)
{
    for( int i = 0;  i * i <= n ; i++ )
     if( IsPrime ( *( l + i) ) )
        setItem( l, n, *(l + i) );      
}

Answer 10

вот простой код для печати всех простых чисел до заданного числа n,

#include<iostream.h>
#include<conio.h>

void main()
{
clrscr();
int n,i,j,k;
cout<<"Enter n\n";
cin>>n;

for(i=1;i<=n;i++)
{   k=0;
  for(j=1;j<=i;j++)
  {
    if((i%j)==0)
    k++;
   }
  if(k==2)
  cout<<i<<endl;
}
getch();
}