Практика программирования (Бейсик, Си, Паскаль)


         

Разложение числа на простые множители


char j=l;

printf("\n Введите целое число: ");
scanf("%ld",&M);
Ml=M/2;

printf("\n%ld=",M);
ml:

if (M % k=0) {

j=0;

M=M/k;

printf("%ld",k) ;
if(M!=l)printf("*"); }

else k++;

if(k<=Ml) goto ml;
if(j==l)
printf("простое число");
getch(); }

Программа 2_20.pas

program razlojenie;

{ Разложение числа на простые множители }

var

M,Ml,k:longint ;
j:boolean;

IF K&<=Ml& THEN GOTO Ml
IF J=0 THEN PRINT " простое число"
END

Программа 2_20,с

/* Разложение числа на простые множители */
#include <stdio.h>
#include <conio.h>

main ()
{

long M,M1,k=2;

char j=l;

printf("\n Введите целое число: ");
scanf("%ld",&M);
Ml=M/2;

printf("\n%ld=",M);
ml:

if(M % k==0)
{

j=0; M=M/k;

printf("%ld",k) ;
if(M!=l) printf("*"); }

else k++;

if(k<=Ml) goto ml;
if(j==l) printf ("простое число");
getch();
}

Программа 2_20.pas

program razlojenie;

{
Разложение числа на простые множители }

var

М,М1,k:longint;

j:boolean;

label 1;
begin

j:=true; k: =2 ;

write('Введите целое число: ');
readln(M);
M1:=M div 2;
write(M,' = ');
1:
if(M mod k)=0 then begin

j:=false;
M:=M div k;
write (k) ;

if Mol then write ('*');
end

else k:=k+l; if k<=Ml then goto 1;
if j then write('простое число'};
readln; end.

Задание 2.21. Проверка числа на "простоту"

Составить функцию prime (п), аргументом которой является длинное целое положительное число. Функция должна возвращать значение true (Паскаль) или 1 (Си, QBasic), если ее аргумент является простым числом. В противном случае функция должна возвращать значение false или о.

Совет 1 (общий)

Один из наиболее легко реализуемых алгоритмов проверки числа на "простоту" заключается в том, что исходное число N последовательно делят на 2, 3, 5, 7, 9, ..., 2*p+l ( (2*p+l)2 < N). Если ни один из остатков отделения не равен нулю, то N — простое. Конечно, этот алгоритм далек от совершенства — например, зачем делить на 9 или 15, если число не делилось на 3. По идее, в проверке должны участвовать только простые делители — 2, 3, 5, 7, 11, 13, ... Но построить такую программу несколько сложнее (см. задание 2.22).

Содержание  Назад  Вперед