singlepost

Язык C. Поиск простых чисел [Решено] << На главную или назад  

Спрошу теперь и я.
Задание было такое:
Даны натуральные числаа,b (а<b).Получить все простые числа p, удовлетворяющие неравенству a<p<b.
Код ниже. Что-то можно оптимизировать?

#include <stdio.h>
int main ()
{
int a,b,j,k;
bool r=true;
printf("a=");
scanf("%d",&a);
if (a<=0) {
printf("what?!\a\n");
return 0;
}
printf("b=");
scanf("%d",&b);
if (b<=0 || b<=a) {
printf("what?!\a\n");
return 0;
}
for (j=a; j<b ; j++)
{
for (k=2; k<=10; k++)
{
if (j!=k)
{
if (j%k!=0 && r==true)
r=true;
else
break;
}
if (k==10 && r==true && j!=1)
printf ("p=%d\n",j);
}
}
return 0;
}

Решение найдено http://vkontakte.ru/topic-8679781_21832071#n7

6 ответов в теме “Язык C. Поиск простых чисел [Решено]”

  1. 1
    Александр Мачехин ответил:

    Сначала в этой программе ошибки исправь. Или допиши условие. Четыре момента оптимизации сразу в глаза бросаются.

  2. 2
    Дмитрий Молостов ответил:

    #2
    Подправил.

    #include <stdio.h>
    int main ()
    {
    int a,b,j,k;
    bool r=true;
    printf("a="); scanf("%d",&a);
    if (a<=0) { printf("what?!\a\n"); return 0; }
    printf("b="); scanf("%d",&b);
    if (b<=0 || b<=a) { printf("what?!\a\n"); return 0; }
    for (j=a; j<b; j++)
    {
    for (k=2; k<=a/2; k++) // тут
    {
    if (j!=k)
    {
    if (j%k!=0 && r==true)
    r=true;
    else
    break;
    }
    if (k==a/2 && r==true && j!=1 && j>a && j<b) // и тут
    printf ("%d\n",j);
    }
    }
    return 0;
    }

    Что то ещё?

  3. 3
    Михаил Афанасьев ответил:

    if (b<=0 || b<=a) // бесполезно первое условие.. если ты a проверил, то оно
    //уже автоматически больше нуля..

  4. 4
    Михаил Афанасьев ответил:

    и чего-то я вообще не понял твою булевскую r. Она кроме как true значения у тебя не принимает. зачем она? если нужна – объясни пожалуйста, мне самому интересно.

  5. 5
    Александр Мачехин ответил:

    Все простые числа (кроме 1, 2 и 3) имеют вид 6*n-1 или 6*n+1, где n – натуральное число. Чётные делители проверять абсолютно бессмысленно. Все косяки, которые есть в данном программе сами уйдут (я насчитал ещё 3). К тому же, делители можно проверять до корня квадратного из текущего числа.
    P.S. плохо подправил. ;)

  6. 6
    Дмитрий Молостов ответил:

    Решение :

    #include <iostream>
    #include <math.h>
    using namespace std;

    int main()
    {
    int a,b,p,i,k;
    bool flag;
    do {
    cout << "a="; cin >> a;
    if (a<=0) { cout << "what?!\n"; }
    } while (a<=0);
    do {
    cout << "b="; cin >> b;
    if (b<=a) { cout << "what?!\n"; }
    } while (b<=a);
    if (b-a==1) cout << "Set of p is empty\n";
    elsecout << "Set of p:\n";

    for (i=a+1; i<b; i++)
    {
    flag=false;
    for (k=2; k<=i; k++)
    {
    if (k==2 && i==2) cout << "2\n";
    if (k<i)
    {
    if (i%k!=0)
    {
    flag=true;
    p=i;
    }
    else break;
    }
    else if (k==i && flag==true)
    cout << p << "\n";
    }
    }
    return 0;
    }

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.