Prime numbers and factorization


Plus
Pin


Problem description Progress
ID 33571. Simplicity test
Темы: Prime numbers and factorization   

Check if a number is prime.

Input 
Enter one natural number n not exceeding 2000000000 and not equal to 1.

Imprint 
Output  string prime if the number is prime, or composite if the number is composite.
 

Examples
# Input Output
1 5 prime

ID 29549. Decomposition into primes - 1
Темы: Prime numbers and factorization   

It is required to decompose the integer N into prime factors, presenting it as a product of prime factors and display the result in ascending order.
 
Input  
The input number N (\(2 <= N <= 10^9\)).
 
Output 
Print a list of prime factors of N in non-decreasing order, separated by «*».
 
Examples
# Input Output
1 5 5
2 30 2*3*5

ID 29548. Decomposition into primes - 2
Темы: Prime numbers and factorization   

It is required to decompose the integer N into prime factors, presenting it as a product of powers of prime factors and output the result in ascending order.
 
Input 
The input is a number N (\(2 <= N <= 10^9\)).
 
Output 
Output prime factorization of N.
 
Examples
# Input Output
1 2 2
2 1008 2^4*3^2*7

ID 21767. Bertrand's postulate
Темы: Prime numbers and factorization   

Bertrand's postulate (Bertrand-Chebyshev theorem, Chebyshev theorem) states that for any \(n > 1\) there is a prime number p in the interval \(n < p < 2n\). Such a conjecture was put forward in 1845 by the French mathematician Joseph Bertrand (who checked it up to \(n=3000000\)) and proved in 1850 by Pafnuty Chebyshev. Ramanuzhan in 1920 found a simpler proof, and Erdős in 1932 – even simpler.

Your task is to solve a somewhat more general – namely, by the number n find the number of prime numbers p from the interval \(n < p < 2n\).

Recall that a number is called prime if it is only divisible by itself and one

Input
Integer n (\(2 <= n <= 50000\)).

Imprint 
Print one number – answer to the problem.

 
Examples
# Input Output
1 3000 353

ID 21768. Prime numbers - 1
Темы: Prime numbers and factorization   

Find the number of all four-digit prime numbers ending in k.

Input 
Number k.

Imprint 
Output a number - the number of prime numbers that satisfy the condition of the problem. If there are no such numbers, then output the word Absent.


Examples
# Input Output
1 1 266
2 0 Absent

ID 33572. Goldbach's hypothesis
Темы: Prime numbers and factorization   

Goldbach's conjecture (until proven) states that any even number (except 2) can be represented as the sum of two prime numbers.

Input  
The program receives as input one natural even number n (\(3<n<2 \cdot 10^5\)).

Imprint 
The program should output two numbers separated by a space. Numbers must be prime and add up to n.
 

Examples
# Input Output
1 4 2 2
2 6 3 3

ID 30756. Triplets of numbers
Темы: Prime numbers and factorization   

Write a program that finds the number of triplets of integers a, c, p such that p — prime number, numbers satisfy the equality: $$ \sqrt{a} - \sqrt{c} = \sqrt{p}. $$ Each of the numbers a, c and p lies between N and M (that is, \(N<=a<= M,\ N<=c<= M,\ N<=p<= M\)).


Input 
Enter two integers N and M (\(0<=N<=M<=100000\) ).
 
Imprint 
Output the desired number of triples of numbers a, c, p.
 
Examples
# Input Output
1 18 1
2 5 20 1
3 1 7 0

ID 32949. Degree of
Темы: Prime numbers and factorization   

For a given natural A find the minimum natural N such that N to the power of N ( N multiplied by itself N times) is divided by A.
 
Input data 
The input is a single number A (\(1 <= A <= 10^9\)).
 
Output
It is necessary to output a single number N.
 
Examples
# Input Output
1 8 4
2 13 13

ID 30773. Простые числа - 2
Темы: Prime numbers and factorization   

Знаете ли вы, что такое простое число? Простое число – это натуральное число, имеющее ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными. Например, числа 2, 3, 5, 7, 11 являются простыми. А числа 4, 6, 10 – составными.
 
Требуется из заданного набора чисел выбрать одно, имеющее максимальное количество простых делителей. Например, 30 имеет три простых делителя (2, 3 и 5), а 40 – только два (2 и 5).
 
Входные данные
Первая строка  содержит число N – количество чисел в наборе. Во второй строке теста содержится N чисел, разделенных пробелом. Все числа во входных данных целые, принимающие значения от 2 до 1024.
 
Выходные данные
В ответе выведите число с максимальным количеством простых делителей. Если таких чисел несколько, выведите наименьшее из них.
 
Ввод Вывод
10
3 5 7 9 11 13 15 17 19 21
15
11
2 4 6 8 10 13 39 105 200 201 143
105

http://acmp.ru/index.asp?main=task&id_task=938

ID 38238. Error
Темы: Whole numbers    Prime numbers and factorization   

Think of 2011 as the sum of K consecutive primes (i.e., primes with no other primes between them). For example, the number 31 can be represented as the sum of three successive prime numbers as follows: 7 + 11 + 13 = 31.

Input
One natural number K is entered (from 1 to 2011).

Imprint
Print the terms in ascending order, separating them with a space.

If it is impossible to expand into a sum of K terms, print NO SOLUTION (in capital letters).

Examples
# Input Output
1 3 661 673 677
2 2 NO SOLUTION

ID 38356. broken calculator
Темы: Prime numbers and factorization   

The calculator has two memory cells: the contents of the first one are always displayed on the display, the second is a buffer. At the initial moment of time, the calculator displays an integer X, and the buffer contains the number 0. The calculator has only two keys: "+" and «=». By clicking on the "+" the number that is currently displayed on the scoreboard is copied to the buffer. When you click on «=» the number from the buffer is added to the number displayed on the scoreboard and the result is displayed on the scoreboard, the number in the buffer does not change.

It is required for the least number of keystrokes on the calculator to ensure that the number Y is displayed on the scoreboard.

Input
The input file contains two integers X and Y. Each of these numbers does not exceed 109 in absolute value.

Imprint
In the first line of the output file print a single number — the number of keystrokes required to obtain the number Y. If it is impossible to obtain the number Y from the number X using the specified operations, output a single number –1 to the output file.

Examples
# Input Output
1 -1 -8 6
2 2 16 6
3 0 0 0

ID 38433. Degree
Темы: Prime numbers and factorization   

In order to check how her students can count, every year Maria Ivanovna gives them the same problem at home — for a given natural A, find the minimum natural N such that N to the power of N (N multiplied by itself N times) is divisible by A. Only the number A changes from year to year and from student to student.
You have decided to help future generations. To do this, you need to write a program that solves this problem.
Input data format
The input file contains a single number A (1 & le; A & le; 1000000000 — just in case; suddenly Maria Ivanovna will set a large number to "fill up" someone).
Output data format
Print the single number N in the output file.
 

Examples
# Input Output
1 8 4
2 13 13

ID 38575. Pseudoprimes
Темы: Prime numbers and factorization   

Let a1 = 2, a2 = 3, an = aa2 ·...·an-1 – 1 for n ≥ 3. We call the numbers ai pseudoprime. For a given natural number X, you need to answer the question: can X be uniquely represented as a product of pseudoprimes (representations that differ only in the order of factors are considered the same), and, if possible — output decomposition.<

Input
One natural number X, 1 < X≤ 109.

Imprint
Print pseudoprimes whose product equals X in any order. If the decomposition does not exist or it is not unique, return 0.
 

Examples
# Input Output
1 6 2 3
2 5 5
3 7 0

ID 38731. Minimum divisor
Темы: Prime numbers and factorization    while loop   

Find the smallest natural divisor of x other than 1 (2 <= x <= 30000).

Input
A natural number x is entered.

Imprint
Print the smallest divisor of x that is different from 1.

Examples
# Input Output
1 6 2

ID 38732. Number Divisors
Темы: for loop    Prime numbers and factorization    Conditional operator   

Print all natural divisors of x in ascending order (including 1 and the number itself).

Input
Enter a natural number x

Imprint
Print all divisors of x

 

Examples
# Input Output
1 32 1 2 4 8 16 32 

ID 38733. Number of divisors
Темы: Prime numbers and factorization    for loop   

Count the number of natural divisors of x (including 1 and the number itself; x2109).

Input
A natural number x is entered.

Imprint
Print a single number - the number of divisors of x.
 

Examples
# Input Output
1 32 6

ID 44036. Balance gifts
Темы: GCD and Euclid's algorithm    Prime numbers and factorization   

Santa Claus has N gift bags. Each bag has a weight of a1, a2, ..., < code>aN. For a uniform load on the sleigh, Santa Claus needs the weight of all bags to be the same. To achieve this, Santa Claus with his magic staff can perform one of the following operations any number of times, possibly zero times.

  • Santa Claus can choose any bag and if its weight is a multiple of two, then reduce the weight by half.
  • Santa Claus can choose any bag and if it is a multiple of three, then reduce the weight by three times.

Santa Claus takes 1 second for each operation.

Find the minimum total number of seconds it takes Santa Claus to reach the same weight of all the gift bags. If there is no way to achieve the goal, print the value -1.

instead

Input
The program takes as input in the first line an integer N (2 <= N <= 1000). The second line contains N numbers ai - the weight of the i-th gift bag (1 <= < code>ai <= 109).


Imprint
Print the answer to the problem.
 
 
Examples
# Input Output
1 3
1 4 3
3
2 3
2 7 6
-1
3 6
1 1 1 1 1 1 
0