고전 c 프로그램(0030)---불가약분수 구하기
/**************************************************************************************
* Function : test
* Create Date : 2014/05/22
* Author : NTSK13
* Email : [email protected]
* Copyright : , 。
*
* Version : V0.1
***************************************************************************************
c (0030) ---
:
Though prime numbers used to belong to pure mathematics traditionally, they’re more related now to our real world thanks to the development of cryptology and computers in late 20th century.
The public-key cryptography has introduced the concept, ‘it is easy to encode but hard to decode,’ increasing the convenience and reliability of the cryptography system.
Another concept, ‘it is easy to calculate but hard to inverse calculate,’ applies to integer factorization.
RSA cryptography system, which uses such a characteristic of integer factorization, encodes by multiplication of p and q (p*q), a very large prime number each, but needs to know what each p and q exactly is to decode it.
For example, it is easy to multiply two five-digit numbers, but in a given formula, ‘p*q = 1459160519,’ it will take long to find the right p and q pair (34583, 42193).
In reality, the numbers used by RSA are prime numbers of hundreds of digits.
For this reason, two issues have gained importance: primality test, which assesses whether a large number is a prime number or not, and prime factorization algorithms of such large numbers.
The cryptography system in development process by our company’s research lab is also based on irreducible fractions where such algorithms can be applied.
Figure out the problem below in order to help us design a safe and easy to use cryptography system that is right for mobile devices.
When a number N is given, use another number (≤ N) and find out all possible irreducible fractions. (≥ 0, ≤ 1)
For example, if N = 5, the number of possible irreducible fractions are 11 as below.
0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1
Time limits: 1 second(java: 2 seconds)
Input format
Input may include many test cases. The number of test cases, T, is given on the first line of input and then the amount of T of test cases is given in a line. (T ≤ 30) N is given for the first line of each test case. (1 ≤ N ≤ 160)
Output Format
Output the number of cases of possible irreducible fractions for the first line of each test case.
Input Example
1
5
Output Example
11
**************************************************************************************/
// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful.
#include <stdio.h>
int main(void)
{
int tc, T;
// The freopen function below opens input.txt file in read only mode, and afterward,
// the program will read from input.txt file instead of standard(keyboard) input.
// To test your program, you may save input data in input.txt file,
// and use freopen function to read from the file when using scanf function.
// You may remove the comment symbols(//) in the below statement and use it.
// But before submission, you must remove the freopen function or rewrite comment symbols(//).
freopen("input.txt", "r", stdin);
// If you remove the statement below, your program's output may not be rocorded
// when your program is terminated after the time limit.
// For safety, please use setbuf(stdout, NULL); statement.
setbuf(stdout, NULL);
scanf("%d", &T);
for(tc = 0; tc < T; tc++)
{
/**********************************/
int ret=0,N=0;
int up=1,down=2,r=0;
int max=0;
int min=0;
scanf("%d", &N);
for(up=2;up<N;up++)
for(down=up+1;down<N+1;down++)
{
//if(down%up ==0 )
// ret++;
max=down;
min=up;
r=max%min;
while(r!=0)
{
max=min;
min=r;
r=max%min;
}
if(min==1)
ret++;
}
/***********************************/
printf("%d
",ret+1+N);
// Print the answer to standard output(screen).
}
return 0;//Your program should return 0 on normal termination.
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.