| Problem description | | Progress |
|
Темы:
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
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
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 | |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
Prime numbers and factorization
Let a1 = 2, a2 = 3, an = a1·a2 ·...·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 |
| |
![]()
|
|
Темы:
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
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
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
| |
![]()
|
|
Темы:
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 |
| |
![]()
|